007. 10001st Prime (k번째 소수 구하기)

​문제 (English)

By listing the first six prime numbers 2,3,5,7,11, and 13, we can see that the 6th prime is 13.

What is the 10001st prime number?

 

Answer: 104743

문제 분석

---

k번째 소수가 무엇인지 찾는 문제이다.

• 2에서부터 시작해서 k번째가 될 때까지 차례대로 소수를 구할 수도 있고,
• 문제에서 물어보는 대략 가장 큰 소수를 알 수 있다면, 에라토스테네스의 체를 이용해서 소수를 구한 후 k번째를 구할 수도 있다.

 

풀이 1 

---

2부터 시작해서 n번째 소수를 찾아보자.

어떤 수 $x$가 소수라면, $x$는 $\sqrt{x}$보다 작은 어떤 수로도(1은 제외) 나누어 떨어지지 않는다.

 

위 원리를 이용해서 어떤 값 $x$에 대해 $\sqrt{x}$ 보다 작은 값 k에 대해 $x % k == 0$인지를 확인해서, 0이 되는 k가 없으면 이때 $x$는 소수로 처리하고, i를 증가시킨다.  이렇게 i를 n이 될 때까지 증가시키면서 $x$를 구하면, 이 $x$가 n번째 소수가 된다.

 

#[test]
fn test(){
    assert_eq!(2, answer(1));
    assert_eq!(3, answer(2));
    assert_eq!(5, answer(3));
    assert_eq!(13, answer(6));
    assert_eq!(104743, answer(10001));  
    
}

#[cfg(test)]
/// - 어떤 수 x가 소수라면, x는 root(x)보다 작은 어떤 수로도(1은 제외) 나누어지지 않는다는 것을 이용해서 소수 찾음
fn answer(n: u64) -> u64{
    let mut ans: u64 = 2;

    let mut i: u64 = 1;
    while i < n {
       ans += 1;
       let kmax: u64 = (ans as f64).sqrt() as u64;
       for k in 2..ans{
           if ans % k == 0 { //ans는 소수가 아니다
               break;
           }else if k > kmax{ //ans는 i+1번째 소수이다.
               i += 1;
               break;
           } 
       }
    }
    return ans;
}

 

풀이 2 

---

풀이 1로도 hackerranker 문제를 통과한다.

 

근데, n번째 소수를 구하는 문제에서 이 n의 범위가 $10^4$ 이내라면, 10001번째 소수를 구하고, 이 소수보다 작은 모든 소수를 구해놓으면, n이 어떤 값이라도 쉽게 n번째 소수를 구할 수 있다.

 

10001번째 소수는 104743이기에, 이 수보다 작은 범위에 대해 에라토스테네스의 체를 이용해서 소수를 구하면 쉽게 n번째 소수를 구할 수 있다.

- 대략 104743보다 작은 에라토스테네스 체를 구해 놓는다.

- n번째 소수를 리턴한다.

 

코드

#[cfg(test)]
fn answer1(n: u64) -> u64{
    let mut ans: u64 = 0;

    let v: Vec<u64> = find_primes(105000);
    let nu: usize = n as usize;
    if v.len() >= nu{
       ans = v[nu-1] as u64;
    }
    return ans;
}

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

   for i in 2..=n as usize{
       if sieve[i] == true {
           for j in (2*i..=n as usize).step_by(i){
               sieve[j] = false;
           }
       }        
   }
   
   // let v = sieve.iter().filter(|&x| *x).enumerate().map(|(i,_)|i as u32).collect();

   let mut v: Vec<u64> = Vec::new();
   for i in 2..=n as usize {
       if sieve[i] {
           v.push(i as u64);
       }
   }

   return v;
}

풀이 3

---

풀이 2에서는 실제 소수에 해당하는 값들을 벡터에 집어 넣었는데, 그렇지 않고 그냥 에라토스테네스의 체까지만 구하고, n번째 소수는 체(sieve) 배열을 이용해서 구하면, 좀 더 빨리 구할 수 있다.

#[cfg(test)]
fn answer2(n: u64) -> u64{
    let mut ans: u64 = 0;

    let v: Vec<bool> = find_primes2(105000);
    let mut j: u64 = 0;
    for i in 0..v.len(){
       if v[i] == true {
           j += 1;
           if j == n {
               ans = i as u64 ;
               break;
           }
       }
    }
    
    return ans;
}

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

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

 

총평

---

소수를 어떻게 구하는지, 소수가 무엇인지를 물어보는 문제이다.

 

전체 소스코드

---

p7.rs 

#[test]
fn test(){
    assert_eq!(2, answer(1));
    assert_eq!(3, answer(2));
    assert_eq!(5, answer(3));
    assert_eq!(13, answer(6));
    assert_eq!(104743, answer(10001));  
    
}

#[cfg(test)]
/// - 어떤 수 x가 소수라면, x는 root(x)보다 작은 어떤 수로도(1은 제외) 나누어지지 않는다는 것을 이용해서 소수 찾음
fn answer(n: u64) -> u64{
    let mut ans: u64 = 2;

    let mut i: u64 = 1;
    while i < n {
       ans += 1;
       let kmax: u64 = (ans as f64).sqrt() as u64;
       for k in 2..ans{
           if ans % k == 0 { //ans는 소수가 아니다
               break;
           }else if k > kmax{ //ans는 i+1번째 소수이다.
               i += 1;
               break;
           } 
       }
    }
    return ans;
}

//---------------------------
//- 에라토트테네스의 체를 이용해서 소수를 구하고, 10001번째를 출력
//- 이 방법은, 10001번째 소수가 대략 얼마인지를 알아야 풀 수 있는 방법임
//- 속도면에서는 조금 빨라지긴한다. 
//  더 큰 소수일수록 체를 이용한 방법이 빠르다. 
#[test]
fn test1(){
    assert_eq!(2, answer1(1));
    assert_eq!(3, answer1(2));
    assert_eq!(5, answer1(3));
    assert_eq!(13, answer1(6));
    assert_eq!(104743, answer1(10001));    
}

#[cfg(test)]
fn answer1(n: u64) -> u64{
    let mut ans: u64 = 0;

    let v: Vec<u64> = find_primes(105000);
    let nu: usize = n as usize;
    if v.len() >= nu{
       ans = v[nu-1] as u64;
    }
    return ans;
}

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

   for i in 2..=n as usize{
       if sieve[i] == true {
           for j in (2*i..=n as usize).step_by(i){
               sieve[j] = false;
           }
       }        
   }

   
   // let v = sieve.iter().filter(|&x| *x).enumerate().map(|(i,_)|i as u32).collect();

   let mut v: Vec<u64> = Vec::new();
   for i in 2..=n as usize {
       if sieve[i] {
           v.push(i as u64);
       }
   }

   return v;
}

//----------------------------------
// 에라토스테네스의 체를 사용하는데, 찾은 소수를 벡터에 저장하지않고, 그냥 체 자체를 리턴후,
// 이 배열값에서 n번째 소수를 찾아보자
// 조금 더 빨라진다.
#[test]
fn test2(){
    assert_eq!(2, answer2(1));
    assert_eq!(3, answer2(2));
    assert_eq!(5, answer2(3));
    assert_eq!(13, answer2(6));
    assert_eq!(104743, answer2(10001));    
}

#[cfg(test)]
fn answer2(n: u64) -> u64{
    let mut ans: u64 = 0;

    let v: Vec<bool> = find_primes2(105000);
    let mut j: u64 = 0;
    for i in 0..v.len(){
       if v[i] == true {
           j += 1;
           if j == n {
               ans = i as u64 ;
               break;
           }
       }
    }
    
    return ans;
}

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

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

 

끝