[백준 / Rust] 6219번: 소수의 자격

문제

6219번: 소수의 자격

농부 존은 소들에게 소수로 차례차례 번호를 매기는 중이다. 베시는 이 번호에서 숫자 D가 몇 번이나 등장하는지 궁금해졌다.

베시를 도와 범위 A..B(A와 B 포함)내에서 숫자 D를 포함하는 소수의 개수를 구해보자.

소수는 두개의 자연수(1과 자기자신)로만 나누어 떨어지는 자연수를 말한다. 소수의 예로는 2,3,5,7,11,13,17,19,23,29.. 가 있다.

입력

세 정수 A, B, D가 주어진다.

출력

주어진 범위 내에서 숫자 D를 포함하는 소수의 개수를 출력한다.

---

문제 이해하기

 A~B 사이의 수 중에서 소수를 찾고 해당 소수에 숫자 D가 포함되어 있는지를 판별하는 문제입니다. 에라토스테네스의 체를 사용하여 먼저 소수인지 여부를 구해주고 소수를 문자열로 변환하여 D를 포함하고 있는지 검사해 주면 됩니다.

---

코드

use std::io::{stdin, stdout, BufWriter, Write};

fn main() {
    let mut writer = BufWriter::new(stdout());
    let mut lines = stdin().lines();

    let (a, b, d) = {
        let nums = split_line_to_numbers(&lines.next().unwrap().unwrap());
        (nums[0], nums[1], nums[2])
    };

    let mut isPrime = vec![true; b as usize + 1];

    isPrime[0] = false;
    isPrime[1] = false;

    let mut i = 2;
    while i * i <= b {
        if isPrime[i as usize] {
            let mut j = i * i;
            while j <= b {
                isPrime[j as usize] = false;
                j += i;
            }
        }
        i += 1;
    }

    let mut ans = 0;

    for i in a..=b {
        if isPrime[i as usize] {
            if i.to_string().contains(&d.to_string()) {
                ans += 1;
            }
        }
    }

    writeln!(writer, "{}", ans).unwrap();
}

fn split_line_to_numbers(s: &str) -> Vec<i32> {
    s.split_whitespace().map(|s| s.parse().unwrap()).collect()
}

시간: 40ms

메모리: 17128 KB
분류: 수학, 정수론, 소수 판정, 에라토스테네스의 체

글에서 수정이 필요한 부분이나 설명이 부족한 부분이 있다면 댓글로 남겨주세요!