010. Summation of Primes (k보다 작은 모든 소수의 합 구하기)

 

​문제 (English)

The sum of the primes below 10 is $2+3+5+7=17$.

Find the sum of all the primes below two million.

 

Answer: 142913828922

문제 분석

어떤 수 n보다 작은 모든 소수의 합을 구하는 문제이다.

n보다 작은 소수를 구할 수 있으면 되고, 소수를 구하는 것 가장 적절할 방법은 에라토스테네스의 체를 이용하는 것이다.

이 체(sieve)를 이용해서 소수들을 구하고, 이 소수들 중에서 n보다 작은 소수에 대한 합을 구하면 된다.

 

풀이 1 

에라토스테네스의 해(Eratesthones Sieve)는 다음과 같이 구한다.

1) 구하고자 하는 최대 소수값이 N이면, N+1 크기만큼의 배열 s를 만든다.  

2) s[0] = s[1] = false

3) i=2에서 sqrt(N)까지의 루프1

    4) 만약 s[i]==true이면, j=2*i에서 N까지의 루프2. 이때 i 만큼씩 step

        5) s[j] = false 

 

i=2에 대해서  {s[4], s[6], s[8], ....}의 값을 false로 처리

i=3에 대해서 {s[6], s[9], s[12],...}의 값을 false로 처리

...

 

루프1에서 sqrt(N)까지만 처리하면 되는 것에 유의.

루프2에서 j=2*i부터 시작하고, i 만큼씩 step 도는 것에 유의

 

위 사항만 유의하면, 그다지 어렵지 않게 구현할 수 있다.

fn get_sieve(max_num:usize) -> Vec<bool> {
    let mut sieve: Vec<bool> = vec![true; max_num+1]; // [0,...,n]
    sieve[0] = false; sieve[1] = false;
    let sqrt_n:usize = (max_num as f64).sqrt() as usize;

    for i in 2..=sqrt_n {
        if sieve[i]{
            for j in (2*i..=max_num).step_by(i){
                sieve[j] = false;
            }
        }
    }    
    return sieve;
}

 

에라토스테네스의 체로부터 소수만을 뽑아서 벡터로 만드는 것은 아래 코드.

fn get_primes(max_num:usize) -> Vec<u64> {
    let sieve = get_sieve(max_num);

    let mut v:Vec<u64> = Vec::new();    
    for j in 1..sieve.len() {
        if sieve[j] { v.push(j as u64); }
    }
    return v;
}

 

이렇게 소수로된 벡터를 구한 후, 원하는 최대 수 N보다 작은 소수의 합을 구하면 된다.

전체 코드는 아래와 같다.

#[test]
fn test(){
    let primes = get_primes(2000000+1); 
    assert_eq!(10, answer(&primes, 5)); //2,3,5
    assert_eq!(17, answer(&primes, 10)); //2,3,5,7
    assert_eq!(142913828922, answer(&primes, 2000000));
}

//에라토스테네스 체 이용 소수구한 후, 해당 번째 이하 합 구하면 된다.
#[cfg(test)]
fn answer(primes:&Vec<u64>, max_num:u64) -> u64 {    
    let mut sum:u64 = 0;
    for i in 0..primes.len() {
        if primes[i] <= max_num {sum += primes[i];}
        else {break; }
    }
    return sum;
}                            

#[cfg(test)]
fn get_sieve(max_num:usize) -> Vec<bool> {
    let mut sieve: Vec<bool> = vec![true; max_num+1]; // [0,...,n]
    sieve[0] = false; sieve[1] = false;
    let sqrt_n:usize = (max_num as f64).sqrt() as usize;

    for i in 2..=sqrt_n {
        if sieve[i]{
            for j in (2*i..=max_num).step_by(i){
                sieve[j] = false;
            }
        }
    }    
    return sieve;
}

#[cfg(test)]
fn get_primes(max_num:usize) -> Vec<u64> {
    let sieve = get_sieve(max_num);

    let mut v:Vec<u64> = Vec::new();    
    for j in 1..sieve.len() {
        if sieve[j] { v.push(j as u64); }
    }
    return v;
}

 

위 코드로 hackerrank를 통과할 수 있다. 

 

hackerrank에 넣을 때는, 각 문제마다 소수 벡터를 구하게 하지 않고, 1000001개의 소수를 구해놓고, 각 문제마다 이 소수벡터를 이용하게 하는 게 더 효율적이다. 

참조로, hackerrank의 소스코드는 아래와 같다.

use std::io::{self, BufRead};
fn main() {
    let stdin = io::stdin();
    let mut stdin_iterator = stdin.lock().lines();

    let t = stdin_iterator.next().unwrap().unwrap().trim().parse::<i32>().unwrap();
    
    let primes = get_primes(1000000+1); 
    for _ in 0..t {
        let n = stdin_iterator.next().unwrap().unwrap().trim().parse::<i32>().unwrap();
        println!("{}",answer(&primes, n as u64));
    }
}

fn answer(primes:&Vec<u64>, max_num:u64) -> u64 {    
    let mut sum:u64 = 0;
    for i in 0..primes.len() {
        if primes[i] <= max_num {sum += primes[i];}
        else {break; }
    }
    return sum;
}                         

fn get_sieve(max_num:usize) -> Vec<bool> {
    let mut sieve: Vec<bool> = vec![true; max_num+1]; // [0,...,n]
    sieve[0] = false; sieve[1] = false;
    let sqrt_n:usize = (max_num as f64).sqrt() as usize;

    for i in 2..=sqrt_n {
        if sieve[i]{
            for j in (2*i..=max_num).step_by(i){
                sieve[j] = false;
            }
        }
    }    
    return sieve;
}

fn get_primes(max_num:usize) -> Vec<u64> {
    let sieve = get_sieve(max_num);

    let mut v:Vec<u64> = Vec::new();    
    for j in 1..sieve.len() {
        if sieve[j] { v.push(j as u64); }
    }
    return v;
}

 

풀이 2 

---

풀이 1로도 충분하다.

그렇지만, 풀이 2에서는 풀이 1에서 작성된 코드 중에서 for 루프로 되어 있는 것을 Iterator Adapter를 사용해서 바꿔본다. 이렇게 했다고 해서 속도가 향상되거나 하진 않는다. 비슷. 단지, 일부 코드는 깔끔해지기 때문에, 연습삼아 해본다.

 

1. 소수중에서 N보다 작은 모든 소수 합치기

기존 코드는,

fn answer(primes:&Vec<u64>, max_num:u64) -> u64 {    
    let mut sum:u64 = 0;
    for i in 0..primes.len() {
        if primes[i] <= max_num {sum += primes[i];}
        else {break; }
    }
    return sum;
}

 

Iterator를 사용한 코드는 아래와 같고, 한 줄로 표현될 수 있어서 깔끔하다.

fn answer1(primes:&Vec<u64>, max_num:u64) -> u64 {    
    primes.into_iter().filter(|&x| *x <= max_num).sum()    
}

into_iter()의 경우 참조값으로 전달되기에, filter에서 &x로 처리한 것에 유의

 

2. 에라토스테네스 체로부터 소수를 뽑아내서 벡터로 만들기

원래 코드는,

fn get_primes(max_num:usize) -> Vec<u64> {
    let sieve = get_sieve(max_num);

    let mut v:Vec<u64> = Vec::new();    
    for j in 1..sieve.len() {
        if sieve[j] { v.push(j as u64); }
    }
    return v;
}

 

Iterator를 사용한 코드는 아래와 같고, 오히려 더 복잡해진 느낌이다.

fn get_primes1(max_num:usize) -> Vec<u64> {
    let sieve = get_sieve1(max_num);

    let v:Vec<u64> = sieve.into_iter()
                    .enumerate().filter(|(_,val)| *val)       //true인 것만   
                    .map(|(i,_)| i)                           //enumerate에서 index를 뽑아냄  
                    .map(|x| x as u64).collect::<Vec<u64>>();    
    return v;    
}

sieve에서 value가 true일 때의 index가 해당 소수가 되는 것이기에, enumerate를 사용해서 index를 뽑아내는 구문에 유의

이때 index가 usize형태이기에 u64로 바꿔야는데, 이 때는 map을 사용하면 됨

 

필자의 경우는, 그냥 for 루프를 쓰는 게 더 편하다. 이 경우 for루프가 속도도 더 빠르지 않을까 하는 생각임.

총평

---

소수를 구하는 방법으로는 에라토스테네스의 체를 이용하는 것이 가장 일반적이기에, 해당 코드를 안 보고도 짤 수 있도록 숙지해둬야 한다. 이때, sqrt(N)까지만 루프를 돌리면 되고, 2*j 부터 false로 체크해 나가면 되는 것에 유의하면 된다.

 

전체 소스코드

---

p10.rs 

#[test]
fn test(){
    let primes = get_primes(2000000+1); 
    assert_eq!(10, answer(&primes, 5)); //2,3,5
    assert_eq!(17, answer(&primes, 10)); //2,3,5,7
    assert_eq!(142913828922, answer(&primes, 2000000));
}

//에라토스테네스 체 이용 소수구한 후, 해당 번째 이하 합 구하면 된다.
#[cfg(test)]
fn answer(primes:&Vec<u64>, max_num:u64) -> u64 {    
    let mut sum:u64 = 0;
    for i in 0..primes.len() {
        if primes[i] <= max_num {sum += primes[i];}
        else {break; }
    }
    return sum;
}                            

#[cfg(test)]
fn get_sieve(max_num:usize) -> Vec<bool> {
    let mut sieve: Vec<bool> = vec![true; max_num+1]; // [0,...,n]
    sieve[0] = false; sieve[1] = false;
    let sqrt_n:usize = (max_num as f64).sqrt() as usize;

    for i in 2..=sqrt_n {
        if sieve[i]{
            for j in (2*i..=max_num).step_by(i){
                sieve[j] = false;
            }
        }
    }    
    return sieve;
}

#[cfg(test)]
fn get_primes(max_num:usize) -> Vec<u64> {
    let sieve = get_sieve(max_num);

    let mut v:Vec<u64> = Vec::new();    
    for j in 1..sieve.len() {
        if sieve[j] { v.push(j as u64); }
    }
    return v;
}

//---------------------------------
// Rust의 Iterator Adapter 이용해서 코드 단순화
#[test]
fn test1(){
    let primes = get_primes1(2000000+1); 
    assert_eq!(10, answer1(&primes, 5)); //2,3,5
    assert_eq!(17, answer1(&primes, 10)); //2,3,5,7
    assert_eq!(142913828922, answer1(&primes, 2000000));
}

//에라토스테네스 체 이용 소수구한 후, 해당 번째 이하 합 구하면 된다.
#[cfg(test)]
fn answer1(primes:&Vec<u64>, max_num:u64) -> u64 {    
    primes.into_iter().filter(|&x| *x <= max_num).sum()    
}                            

#[cfg(test)]
fn get_sieve1(max_num:usize) -> Vec<bool> {
    let mut sieve: Vec<bool> = vec![true; max_num+1]; // [0,...,n]
    sieve[0] = false; sieve[1] = false;
    let sqrt_n:usize = (max_num as f64).sqrt() as usize;

    for i in 2..=sqrt_n {
        if sieve[i]{
            for j in (2*i..=max_num).step_by(i){
                sieve[j] = false;
            }
        }
    }    
    return sieve;
}

#[cfg(test)]
fn get_primes1(max_num:usize) -> Vec<u64> {
    let sieve = get_sieve1(max_num);

    let v:Vec<u64> = sieve.into_iter()
                    .enumerate().filter(|(_,val)| *val)       //true인 것만   
                    .map(|(i,_)| i)                           //enumerate에서 index를 뽑아냄  
                    .map(|x| x as u64).collect::<Vec<u64>>();    
    return v;    
}

 

끝