[Rust로 백준 하루 하나] 15-6. 소수 구하기

문제 (1929번)

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

 

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

 

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

---

풀이

코드

use std::io::{self, BufReader, BufRead, BufWriter, Write};
use std::f64;

fn main() {
    let mut reader = BufReader::new(io::stdin().lock());
    let mut writer = BufWriter::new(io::stdout().lock());

    let mut input = String::new();
    reader.read_line(&mut input).unwrap();
    let mut input_iter = input
        .trim()
        .split_whitespace()
        .map(|i| i.parse::<u32>().unwrap());
    let m = input_iter.next().unwrap();
    let n = input_iter.next().unwrap();

    for i in m..=n {
        if is_prime(i) {
            writeln!(writer, "{}", i).unwrap();
        }
    }
}

fn is_prime(n: u32) -> bool {
    if n < 2 {
        false
    } else {
        for x in 2..=((n as f64).sqrt() as u32) {
            if n % x == 0 { return false; }
        }
        true
    }
}

해설

에라토스테네스의 체를 사용하여 풀어보려고 하였으나 시간이 너무 오래 걸려 제곱근까지 직접 나누는 방식으로 풀었습니다. 에라토스 테네스의 체로 푸는 방법은 추가 학습에서 다루겠습니다.

---

추가 학습

다음과 같이 에라토스테네스의 체를 구현할 수 있습니다.

let mut is_prime = vec![true; n + 1];
is_prime[0] = false;
is_prime[1] = false;

// 에라토스테네스의 체 구현
for i in 2..=((n as f64).sqrt() as usize) {
  if is_prime[i] {
    for j in (i * i..=n).step_by(i) {
      is_prime[j] = false;
    }
  }
}

 

참고로, step_by 메서드는 step 만큼 건너뛰는 함수입니다.

fn step_by(self, step: usize) -> StepBy<Self>
where Self: Sized,

https://doc.rust-lang.org/beta/std/iter/trait.Iterator.html#method.step_by