이 Rust 예제는 찾은 소수를 저장하고 그 수들로 시행 나눗셈을 합니다. primes_up_to(max)는 상한을 포함한 소수 목록을 반환합니다. 1000 이하에는 소수가 168개 있으며 0과 1은 소수가 아닙니다. 체를 구현한 코드는 아닙니다.

코드

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

fn primes_up_to(max: usize) -> Vec<usize> {
    if max < 2 {
        return Vec::new();
    }
    let mut primes = vec![2];
    let mut n = 3;
    while n <= max {
        let mut is_prime = true;
        for &p in &primes {
            if p > n / p {
                break;
            }
            if n % p == 0 {
                is_prime = false;
                break;
            }
        }
        if is_prime {
            primes.push(n);
        }
        if max - n < 2 {
            break;
        }
        n += 2;
    }
    primes
}

fn main() {
    for p in primes_up_to(1000) {
        println!("{}", p);
    }
}

실행과 작은 상한

primes.rs로 저장하고 rustc --edition=2021 primes.rs -o primes로 컴파일합니다. Windows에서는 실행 파일 이름을 primes.exe로 지정합니다. 실행하면 168줄을 출력하며 첫 수는 2, 마지막 수는 997입니다. 이 예제는 Rust 1.90.0에서 실행했습니다.

primes_up_to(0)과 primes_up_to(1)은 빈 벡터를 반환합니다. primes_up_to(2)는 [2], primes_up_to(3)은 [2, 3], primes_up_to(10)은 [2, 3, 5, 7]을 반환합니다. 매개변수 타입 usize는 음수 상한을 포함하지 않습니다. 표준 입력을 해석하는 프로그램은 아닙니다.

판별과 반복문의 원리

1. 상한이 2보다 작으면 빈 결과를 반환합니다. 그렇지 않으면 2를 저장하고 3부터 상한까지의 홀수 후보만 판별합니다. 후보를 처리하기 전에 상한을 확인하므로 상한이 2일 때 3을 추가하지 않습니다.
2. 합성수 후보 n에는 제곱근 이하의 소인수가 있습니다. 그 소수들은 더 작은 후보를 처리하면서 이미 목록에 들어왔습니다. 나눗셈의 나머지가 0이면 후보를 합성수로 판정하고 끝냅니다. 약수를 찾지 못한 상태에서 p > n / p가 되면 더 나눌 필요가 없습니다. 양의 정수 나눗셈으로 제곱근 조건을 표현하므로 p * p나 부동소수점 제곱근을 계산하지 않습니다.
3. for &p in &primes는 목록을 빌려 참조를 차례로 받고 각 usize 값을 p에 복사합니다. 이 반복문이 끝난 뒤에만 새 소수를 추가합니다. 마지막 for p in primes_up_to(1000)은 반환된 벡터에서 값을 꺼내 출력합니다. Rust Vec 문서는 빌린 벡터를 순회하는 경우와 소유한 벡터의 값을 꺼내며 소비하는 경우를 구분합니다.
4. n <= max 안에서는 max - n이 음수가 되지 않습니다. 남은 거리가 2보다 작으면 더하기 전에 끝내고, 그렇지 않을 때만 n += 2를 수행합니다. 따라서 상한을 넘어가는 증가를 피합니다.

적용 범위

상한을 1000으로 고정한 원래 프로그램도 소수 168개를 올바르게 출력합니다. 다만 상한만 0, 1, 2로 바꾸면 처리 전에 상한을 확인하지 않아 범위를 벗어난 2나 3을 출력합니다. 여기서는 재사용 가능한 함수로 정리하면서 이 경계를 처리했습니다.

목록은 발견한 소수마다 usize 하나를 저장합니다. 벡터의 관리 정보와 할당 용량도 메모리를 사용합니다. 나눗셈 한 번을 한 연산으로 세면 시행 나눗셈 횟수의 대략적인 상한을 O(max sqrt(max))로 볼 수 있습니다. 실측 시간이나 비트 복잡도는 아닙니다. 상한이 커질수록 시간과 저장 공간이 더 필요하며, 임의로 큰 상한까지 빠르게 나열한다는 보장은 없습니다. 넓은 구간에는 에라토스테네스의 체 글도 참고하세요. 암호용 소수 생성기는 아닙니다.