37. Truncatable Primes [쪼게도 소수가되는 수 찾기]

​문제 (English)

The number 3797 has an interesting property. Being prime itself, it is possible to continuously remove digits from left to right, and remain prime at each stage: 3797, 797, 97, and 7. Similarly we can work from right to left: 3797, 379, 37, and 3.

Find the sum of the only eleven primes that are both truncatable from left to right and right to left.

NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.

 

Answer: 748317

문제 분석

---

소수 3797을 왼쪽 편에서 한 자리씩 없애면서 3797, 797, 97, 7로 만들어도 모두 소수이고, 오른편에서 한 자리씩 없애면서 3797, 379, 37, 3 처럼 만들어도 모두 소수이다. 이런 수를 작은 수에서부터 차례로 11개를 찾아서 더하라는 문제.

 

풀이 1 

---

소수를 찾을 수 있어야 하겠고, 이 수를 한 자리씩 짜르면서 새로운 수를 만들어 내고, 이 새로운 수가 소수인지 판별하면 되겠다.

 

소수를 찾는 것은 에라토스테네스의 체를 만들면 되겠고, 소수의 판별도 이 체(sieve)를 이용하면 되겠음.

1) 100만 정도까지 에라토스테네스 체를 만든다.

2) 13에서부터 시작해서 한 자리씩 짤라서 새로운 수를 만들어도 소수인지 판별한다.

 

에라토스테네스 코드는 아래와 같다.

fn get_sieve(n:usize) -> Vec<bool> {
    let mut v:Vec<bool> = vec![true;n];
    v[0] = false; v[1] = false;
    let sqrt_n:usize = (n as f32).sqrt() as usize;
    for i in 2..=sqrt_n {
        if v[i] == false {continue;}
        for j in ((i*i)..n).step_by(i){
            v[j] = false;
        }
    }
    return v;
}

• 첫 번째 for 루프에서 2..=sqrt_n 으로 한 것에 유의
• 두 번째 for 루프에서 i*i 부터 시작해도 됨에 유의. 그리고 step_by(i) 한 것도.

이제 소수는 찾았고, 작은 소수에서부터 하나씩 검사해 보면 된다. 

문제 조건에서 한 자리 소수는 제외한다고 했고, 11, 13, 15, 17은 '1'이 들어가기에 무조건 조건을 만족시킬 수 없을 것이다. 해서 23부터 시작해 보면 되겠음

 

그런데, 해당 소수에 대해서 어떻게 왼쪽부터 한자리씩 없애면서 수를 만들 수 있을까?

 

3797의 경우, 이렇게 하면 되겠다.

3797 % 10 = 7,  3797 % 100 = 97, 3797 % 1000 = 797

 

오른쪽부터 없애는 방법은,

3797 / 10 = 379, 3797 / 100 = 37, 3797 / 1000 = 3

 

이렇게 수를 만들면서 sieve 배열을 이용해서 소수인지 판별하면 되겠다.

fn is_truncatable(n:usize, sieve:&Vec<bool>) -> bool {   
    let mut div = 10;
    while div < n {
        if !sieve[n % div] || !sieve[n / div] {return false;}
        div *= 10;
    }
    return true;
}

 

풀이 1에 대한 전체 코드는 아래와 같다.

#[test]
fn test(){
    let sieve = get_sieve(1000000);
    assert_eq!(60, solve(2, &sieve));
    assert_eq!(748317, solve(11, &sieve));
}

#[cfg(test)]
fn solve(cnt_limit:usize, sieve:&Vec<bool>) -> usize {
    let mut v:Vec<usize> = Vec::new();
    let mut cnt:usize = 0;
    let mut i:usize = 23;
    while cnt < cnt_limit && i < sieve.len(){
        if sieve[i] && is_truncatable(i, sieve) {
            v.push(i); cnt += 1;
        }
        i += 1;
    }
    println!("{:?}",v);
    return v.into_iter().sum();
}

#[cfg(test)]
fn is_truncatable(n:usize, sieve:&Vec<bool>) -> bool {   
    let mut div = 10;
    while div < n {
        if !sieve[n % div] || !sieve[n / div] {return false;}
        div *= 10;
    }
    return true;
}

#[cfg(test)]
fn get_sieve(n:usize) -> Vec<bool> {
    let mut v:Vec<bool> = vec![true;n];
    v[0] = false; v[1] = false;
    let sqrt_n:usize = (n as f32).sqrt() as usize;
    for i in 2..=sqrt_n {
        if v[i] == false {continue;}
        for j in ((i*i)..n).step_by(i){
            v[j] = false;
        }
    }
    return v;
}

풀이 2 

---

HackerRank에서는 $100 \le N \le 10^{6}$까지의 수에 대해서, 조건을 만족하는 모든 소수의 합을 구하는 문제이다.

해서, Proejct Euler 문제에서의 11개까지의 소수를 찾는 것이 아니라, N까지의 범위에서 답을 찾는 것으로만 바꾸면 된다.

 

#[test]
fn test1(){
    let sieve = get_sieve(1000000);
    assert_eq!(186, solve1(100, &sieve));
    assert_eq!(748317, solve1(1000000, &sieve));
}

#[cfg(test)]
fn solve1(limit:usize, sieve:&Vec<bool>) -> usize {
    let mut v:Vec<usize> = Vec::new();    
    let mut i:usize = 23;
    while i < limit{
        if sieve[i] && is_truncatable(i, sieve) {
            v.push(i); 
        }
        i += 1;
    }    
    return v.into_iter().sum();
}

 

총평

---

에라토스테네스의 체를 구현할 수 있고, 어떤 수에 대해서 한 자리씩 없애나가서 만들어지는 수를 구현할 수 있으면, 쉽게 풀 수 있는 문제.

 

전체 소스코드

---

p37.rs 

#[test]
fn test(){
    let sieve = get_sieve(1000000);
    assert_eq!(60, solve(2, &sieve));
    assert_eq!(748317, solve(11, &sieve));
}

#[cfg(test)]
fn solve(cnt_limit:usize, sieve:&Vec<bool>) -> usize {
    let mut v:Vec<usize> = Vec::new();
    let mut cnt:usize = 0;
    let mut i:usize = 23;
    while cnt < cnt_limit && i < sieve.len(){
        if sieve[i] && is_truncatable(i, sieve) {
            v.push(i); cnt += 1;
        }
        i += 1;
    }
    println!("{:?}",v);
    return v.into_iter().sum();
}

#[cfg(test)]
fn is_truncatable(n:usize, sieve:&Vec<bool>) -> bool {   
    let mut div = 10;
    while div < n {
        if !sieve[n % div] || !sieve[n / div] {return false;}
        div *= 10;
    }
    return true;
}

#[cfg(test)]
fn get_sieve(n:usize) -> Vec<bool> {
    let mut v:Vec<bool> = vec![true;n];
    v[0] = false; v[1] = false;
    let sqrt_n:usize = (n as f32).sqrt() as usize;
    for i in 2..=sqrt_n {
        if v[i] == false {continue;}
        for j in ((i*i)..n).step_by(i){
            v[j] = false;
        }
    }
    return v;
}

//------------
#[test]
fn test1(){
    let sieve = get_sieve(1000000);
    assert_eq!(186, solve1(100, &sieve));
    assert_eq!(748317, solve1(1000000, &sieve));
}

#[cfg(test)]
fn solve1(limit:usize, sieve:&Vec<bool>) -> usize {
    let mut v:Vec<usize> = Vec::new();    
    let mut i:usize = 23;
    while i < limit{
        if sieve[i] && is_truncatable(i, sieve) {
            v.push(i); 
        }
        i += 1;
    }    
    return v.into_iter().sum();
}

 

끝