Rust 강좌 2. 프라임 - 소수와 친해지기

 

 

새로운 프로그래밍 언어를 배우기 시작할 때, 저는 항상 프로젝트 오일러 문제에 대한 여러 가지 해결책을 코드로 작성하는 것을 좋아합니다.

 

이 문제들은 수학 중심적이어서 일반적인 프로그래밍 입문으로는 최선의 선택은 아닐 수 있지만, 시작하기에는 좋습니다.

 

어쨌든, 문제를 푸는 것이 정말 재미있거든요! (...그리고 힘으로 푸는 것보다 빠르게 푸는 것이 훨씬 더 재미있죠.)

 

많은 프로젝트 오일러 문제는 어떤 식으로든 소수와 관련이 있습니다. n번째 소수를 찾거나, 효율적인 소인수분해를 하거나, 어떤 숫자가 소수인지 아닌지를 확인하는 등의 문제들이죠.

 

물론 이러한 수학적 절차를 직접 코드로 작성할 수도 있지만, 저는 게으른 편입니다.

 

그래서 기존에 만들어진 코드를 찾아 나섰고, 후온 윌슨(Huon Wilson)의 primal 라이브러리를 발견했습니다.

 

우연히도 이것은 제가 Rust 프로그램에서 처음으로 사용한 외부 라이브러리였습니다.

 

crates.io가 생기기도 전, slow_primes라고 불리던 시절부터 사용했죠.

 

자, 그럼 이제 이 라이브러리에 어떤 기능이 있는지 살펴볼까요?

 

소수 체계(Prime Sieve)

소수를 찾기 위한 첫 번째 단계는 소수 체계를 만드는 것입니다.

 

(알고리즘에 대한 자세한 설명은 위키피디아의 에라토스테네스의 체를 참조하세요.) 소수 체계는 특정 범위 내의 모든 소수를 찾아내는 방법입니다.

 

먼저, 우리는 체의 상한을 설정해야 합니다.

 

이 상한을 추정하는 영리한 방법이 있지만 (estimate_nth_prime 문서 참조), 간단하게 지금은 10000으로 하드코딩하겠습니다.

 

이제 실제로 몇 개의 숫자가 소수인지 확인해 보겠습니다:

// day2.rs

extern crate primal;

use primal::Sieve;

fn main() {
    let sieve = Sieve::new(10000);
    let suspect = 5273;
    println!("{}는 소수인가요?: {}", suspect, sieve.is_prime(suspect));
    let not_a_prime = 1024;
    println!("{}는 소수인가요?: {}", not_a_prime, sieve.is_prime(not_a_prime));

    // ... (아래 코드 계속)
}

 

1000번째 소수를 찾는 것도 해볼까요?

// day2.rs (main 함수 내부)

    let n = 1000;
    match sieve.primes_from(0).nth(n - 1) {
        Some(number) => println!("{}번째 소수는 {}", n, number),
        None => println!("{}번째 소수에 대한 정보가 없습니다.", n),
    }
    println!("{:?}", sieve.factor(2610));
}

 

primes_from() 메서드는 이 체에 의해 생성된 모든 소수에 대한 반복자를 반환합니다(2, 3, 5, 7...). Rust의 반복자는 많은 유용한 메서드를 가지고 있습니다.

 

nth() 메서드는 처음 n개의 반복을 건너뛰고 n번째 요소를 반환합니다(반복자가 소진되면 None을 반환합니다).

 

인자는 0부터 시작하므로 1000번째 소수를 찾으려면 999를 nth()에 전달해야 합니다.

 

소인수분해(Factorization)

소인수분해는 숫자를 그 숫자의 약수, 특히 소수 약수로 분해하는 방법입니다.

 

예를 들어, 2610 = 2 * 3 * 3 * 5 * 29입니다. primal API를 사용하여 이를 찾는 방법은 다음과 같습니다:

// day2.rs (main 함수 내부)

    println!("{:?}", sieve.factor(2610));
}

 

이 코드를 실행하면 다음과 같은 결과를 얻습니다:

$ cargo run
Ok([(2, 1), (3, 2), (5, 1), (29, 1)])

 

이게 무슨 뜻일까요? factor()의 결과 타입을 살펴봅시다:

type Factors = Vec<(usize, usize)>;
fn factor(&self, n: usize) -> Result<Factors, (usize, Factors)>

 

조금 복잡해 보이지만, Result 타입을 기억하세요.

 

Ok 변형은 숫자 쌍의 벡터를 래핑합니다. 각 쌍은 소인수와 그 지수(소인수분해에서 몇 번 나타나는지)를 포함합니다. 오류가 발생하면 (남은 값, 부분 소인수분해) 쌍을 받게 됩니다.

 

우리는 소인수분해를 사용하여 (합성 약수를 포함한) 약수의 총 개수를 찾을 수 있습니다.

 

이는 수론에서 매우 중요한 개념입니다. (자세한 이유는 이 블로그의 범위를 벗어나므로 생략합니다.)

 

다음과 같은 함수를 생각해 보세요:

// day2.rs

fn num_divisors(n: usize, primes: &Sieve) -> Option<usize> {
    match primes.factor(n) {
        Ok(factors) => Some(factors.into_iter().fold(1, |acc, (_, x)| acc * (x + 1))),
        Err(_) => None,
    }
}

 

여기서 핵심은 모든 소인수 지수를 곱하기 전에 1씩 증가시키는 것입니다.

 

궁금하신 분들은 Maths Challenge에서 자세한 설명을 확인해보세요.

 

2610 예제에 대해 이 함수를 호출하면 결과로 Some(24)를 얻게 됩니다.

 

즉, 2610은 총 24개의 약수를 가지고 있습니다.

// day2.rs (main 함수 내부)

    println!("{:?}", num_divisors(2610, &sieve));
}

 

프로젝트 오일러 공식 설명

 

프로젝트 오일러 문제에서 약수의 개수를 구하는 공식은 다음과 같습니다.

 

어떤 숫자 N이 소인수분해 되었을 때,

N = p₁^a₁ * p₂^a₂ * ... * p_n^a_n

(p_i는 서로 다른 소수, a_i는 각 소수의 지수)

 

이때, N의 약수의 개수는 다음과 같이 구할 수 있습니다.

 

약수의 개수 = (a₁ + 1) * (a₂ + 1) * ... * (a_n + 1)

 

예시:

2610을 소인수분해하면 2¹ * 3² * 5¹ * 29¹ 입니다.

 

따라서 2610의 약수의 개수는 (1+1) * (2+1) * (1+1) * (1+1) = 2 * 3 * 2 * 2 = 24 개 입니다.

 

왜 이 공식이 성립할까요?

 

약수는 N의 소인수들을 곱해서 만들어집니다. 각 소인수 p_i는 약수 안에 0번부터 a_i번까지 포함될 수 있습니다.

 

즉, 각 소인수에 대해 (a_i + 1) 개의 선택지가 있는 것입니다. 따라서 모든 소인수에 대한 선택지를 곱하면 약수의 총 개수를 구할 수 있습니다.