35. Circular Primes [순환해도 소수가 되는 수 찾기]

 

 

​문제 (English)

The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.

There are thirteen such primes below 100: 2,3,5,7,11,13,17,31,37,71,73,79, and 97. How many circular primes are there below one million?

 

Answer: 55

문제 분석

---

어떤 소수는 각 자릿수를 이동시켜 순환 수를 만들었을 때도 모두 소수가 될 수 있다. 예를 들어 197이라는 수를 순환시키면 {197, 971, 719}가 되는데, 이 세 수가 모두 소수이다.

100만 미만의 이러한 소수를 모두 찾아서 세는 것이 문제.

 

100만 미만의 소수를 찾는 것은 에라토스테네스의 체를 이용해서 구하면 되겠고, 각 소수에 대해서 순환수를 구해서, 해당 순환수가 소수인지 판별하면서 문제를 풀면 되겠다.

 

풀이 1 

---

다음과 같이 풀면 되겠다.

1) 100만 이하의 모든 소수를 찾는다. 에라토스테네스의 체 방법 이용해서 sieve만 구한다.

2) $sieve[x]=true$인 것이 소수이기에, 이 $x$에 대해서 순환수를 구한다. 

3) 순환수는 일종의 조합이기에, 스택을 이용하여 모든 순환수를 구한다.

4) 순환수가 모두 소수인지를 판단한다. 이때 sieve를 이용하면 될 것이다.

 

먼저 에라토스테네스의 체 방법을 이용해서 소수를 구하면,

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

• 첫 번째 for 루프에서 2부터 시작해서 sqrt_n 까지만 수행해도 됨에 유의
• 두 번째 for 루프에서는 시작을 i*i부터 시작하는 것이 중요

순환수를 구하는 것은 permutation을 구하는 것과 유사하다. 

3자리 수라면 depth가 {0,1,2}가 되겠고, 각 depth 자리에 인덱스가 들어가는데, 첫 번째 depth에 들어가는 값이 0이라면 그다음 depth에 들어가는 것은 인덱스 1이 된다. 즉, 하나 커지는 것. 

인덱스가 2를 초과하게되면 다시 0으로 가게 하면 된다.

fn get_permu(input:&Vec<usize>) -> Vec<Vec<usize>> {
    let mut out:Vec<Vec<usize>> = Vec::new(); 
    let mut s:Vec<(usize,usize)> = Vec::new(); //stack
    let mut buf:Vec<usize> = vec![0;input.len()]; //buffer
    
    for i in 1..input.len() {s.push((0,i));}; //except first one
    while s.len() > 0 {
        let node = s.pop().unwrap();
        let d = node.0; let v = node.1;
        buf[d] = v;
        if d == input.len() - 1 { 
            let mut tmp:Vec<usize> = vec![0;input.len()];
            for i in 0..buf.len() {tmp[i] = input[buf[i]];}
            out.push(tmp); 
            continue;
        }
        let n = input.len();  s.push((d+1, (v+1)%n));
    }
    return out;
}

• 처음에 스택에 첫 번째 자리 인덱스만 제외하고 다 넣는다. 이는 이미 소수에 대해서만 순환수를 구하는 것이기에, 원래의 수가 되는 것은 검사할 필요가 없기에, 아예 순환수 리스트에 넣지 않는 것
• depth가 input.len()-1 이 될 때, buf에 있는 인덱스들을 이용해서 순환수를 만들면 됨
• 스택에 인덱스를 넣을 때는, 인덱스가 순환될 수 있게 (v+1)% n을 한다.

이제 sieve로 구한 모든 소수와, 이 소수에 대한 순환수에 대해서 소수가 되는지를 조사하면 된다.

fn solve(n:usize) -> usize {
    // let set = get_prime_set(n);
    let sieve = get_prime_sieve(n);

    let mut v:Vec<usize> = Vec::new();
    for i in 0..n {
        if sieve[i] && is_all_prime(i, &sieve) {v.push(i);}
    }
    println!("{:?}",v);
    return v.into_iter().count(); 
}

fn is_all_prime(a:usize, sieve:&Vec<bool>) -> bool {
    let ditit_a:Vec<usize> = to_digit(a);

    //get all permutation except own number
    let all_permu:Vec<Vec<usize>> = get_permu(&ditit_a);
    for v in all_permu{
        let num = to_num(&v);
        if num > sieve.len() || !sieve[num] {return false;}
    }
    return true;
}

• to_digit 함수는 숫자를 각 자리의 digit로 바꿔주는 함수 (아래 전체코드 참조)
• to_num 함수는 각 digit를 이용해서 숫자로 바꿔주는 함수 (아래 전체코드 참조)

 

 

문제에 대한 소스코드는 아래와 같다.

#[test]
fn test(){
    assert_eq!(5,solve(20));
    assert_eq!(13,solve(100));
    assert_eq!(55,solve(1000000));
}

#[cfg(test)]
fn solve(n:usize) -> usize {
    // let set = get_prime_set(n);
    let sieve = get_prime_sieve(n);

    let mut v:Vec<usize> = Vec::new();
    for i in 0..n {
        if sieve[i] && is_all_prime(i, &sieve) {v.push(i);}
    }    
    return v.into_iter().count(); 
}

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


#[test]
fn is_all_prime_test(){
    let sieve = get_prime_sieve(20);
    let ans = is_all_prime(19, &sieve);
}

#[cfg(test)]
fn is_all_prime(a:usize, sieve:&Vec<bool>) -> bool {
    let ditit_a:Vec<usize> = to_digit(a);

    //get all permutation except own number
    let all_permu:Vec<Vec<usize>> = get_permu(&ditit_a);
    for v in all_permu{
        let num = to_num(&v);
        if num > sieve.len() || !sieve[num] {return false;}
    }
    return true;
}

#[test]
fn get_permu_test(){
    let a:usize = 123;
    let digit = to_digit(a);
    println!("digit: {:?}",digit);

    let v = get_permu(&digit);
    println!("get_permu: {:?}",v);
}

#[cfg(test)]
fn get_permu(input:&Vec<usize>) -> Vec<Vec<usize>> {
    let mut out:Vec<Vec<usize>> = Vec::new(); 
    let mut s:Vec<(usize,usize)> = Vec::new(); //stack
    let mut buf:Vec<usize> = vec![0;input.len()]; //buffer
    
    for i in 1..input.len() {s.push((0,i));}; //except first one
    while s.len() > 0 {
        let node = s.pop().unwrap();
        let d = node.0; let v = node.1;
        buf[d] = v;
        if d == input.len() - 1 { 
            let mut tmp:Vec<usize> = vec![0;input.len()];
            for i in 0..buf.len() {tmp[i] = input[buf[i]];}
            out.push(tmp); 
            continue;
        }
        let n = input.len();  s.push((d+1, (v+1)%n));
    }
    return out;
}


#[cfg(test)]
fn to_digit(mut a:usize) -> Vec<usize> {
    let mut v:Vec<usize> = Vec::new();
    while a > 0 {
        v.push(a % 10);
        a /= 10;
    }
    return v;
}

#[cfg(test)]
fn to_num(v:&Vec<usize>) -> usize {
    let mut a:usize = 0;
    let mut p:usize = 1;
    for i in 0..v.len(){
        a += v[i] * p;
        p *= 10;
    }
    return a;
}

 

풀이 2 

---

HackerRand에서는 n 미만의 수에 대해 소수 및 그 순환수가 모두 소수인 것에 대해 합을 구하하고 되어 있다. 

따라서, Euler Project에 대한 풀이에서 개수가 아닌 합을 구하는 것으로만 바꿔주면 되겠다.

fn solve1(n:usize) -> usize {   
    let sieve = get_prime_sieve(n);
    let mut v:Vec<usize> = Vec::new();
    for i in 0..n {
        if sieve[i] && is_all_prime(i, &sieve) {v.push(i);}
    }    
    return v.into_iter().sum();
}

 

풀이 3

---

풀이 1과 풀이 2 방식만으로도 충분히 빠르지만, 좀 더 생각을 해보면,

어떤 소수에 대해 그 순환수가 모두 소수가 되려면, 해당 소수의 digit 중에 짝수가 있으면 안 되겠다.

 

예를 들어 29의 경우 2가 짝수이기에 제외시켜도 되는 수이다. 즉, 순환수 92가 되었을 때 짝수가 되기에 무조건 소수가 안된다.

따라서, 소수에 대해서 순환수를 뽑아내기 전에, 해당 소수의 각 digit 중에 짝수가 있는지를 판별해서 제외해 버리면, 대상이 되는 수가 적어져서 좀 더 빨리 답을 구할 수 있겠다.

 

fn is_all_prime2(a:usize, sieve:&Vec<bool>) -> bool {
    let ditit_a:Vec<usize> = to_digit(a);
    if a > 2 && contains_even(&ditit_a) {return false;}

    //get all permutation except own number
    let all_permu:Vec<Vec<usize>> = get_permu(&ditit_a);
    for v in all_permu{
        let num = to_num(&v);
        if num > sieve.len() || !sieve[num] {return false;}
    }
    return true;
}

• a > 2인 수에 대해서만 확인한 것에 유의. 2는 소수이면서, 각 digit에 짝수가 있는 셈이어서 소수가 안될 것처럼 보이지만, 소수이기 때문. 2보다 큰 소수에 대해서는 이러한 예외 경우가 없다.

총평

---

소수를 구할 수 있는지, 순환수를 구할 수 있는지를 물어보는 문제

 

전체 소스코드

---

p35.rs 

#[test]
fn test(){
    assert_eq!(5,solve(20));
    assert_eq!(13,solve(100));
    assert_eq!(55,solve(1000000));
}

#[cfg(test)]
fn solve(n:usize) -> usize {
    // let set = get_prime_set(n);
    let sieve = get_prime_sieve(n);

    let mut v:Vec<usize> = Vec::new();
    for i in 0..n {
        if sieve[i] && is_all_prime(i, &sieve) {v.push(i);}
    }    
    return v.into_iter().count(); 
}

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


#[test]
fn is_all_prime_test(){
    let sieve = get_prime_sieve(20);
    let ans = is_all_prime(19, &sieve);
}

#[cfg(test)]
fn is_all_prime(a:usize, sieve:&Vec<bool>) -> bool {
    let ditit_a:Vec<usize> = to_digit(a);

    //get all permutation except own number
    let all_permu:Vec<Vec<usize>> = get_permu(&ditit_a);
    for v in all_permu{
        let num = to_num(&v);
        if num > sieve.len() || !sieve[num] {return false;}
    }
    return true;
}

#[test]
fn get_permu_test(){
    let a:usize = 123;
    let digit = to_digit(a);
    println!("digit: {:?}",digit);

    let v = get_permu(&digit);
    println!("get_permu: {:?}",v);
}

#[cfg(test)]
fn get_permu(input:&Vec<usize>) -> Vec<Vec<usize>> {
    let mut out:Vec<Vec<usize>> = Vec::new(); 
    let mut s:Vec<(usize,usize)> = Vec::new(); //stack
    let mut buf:Vec<usize> = vec![0;input.len()]; //buffer
    
    for i in 1..input.len() {s.push((0,i));}; //except first one
    while s.len() > 0 {
        let node = s.pop().unwrap();
        let d = node.0; let v = node.1;
        buf[d] = v;
        if d == input.len() - 1 { 
            let mut tmp:Vec<usize> = vec![0;input.len()];
            for i in 0..buf.len() {tmp[i] = input[buf[i]];}
            out.push(tmp); 
            continue;
        }
        let n = input.len();  s.push((d+1, (v+1)%n));
    }
    return out;
}


#[cfg(test)]
fn to_digit(mut a:usize) -> Vec<usize> {
    let mut v:Vec<usize> = Vec::new();
    while a > 0 {
        v.push(a % 10);
        a /= 10;
    }
    return v;
}

#[cfg(test)]
fn to_num(v:&Vec<usize>) -> usize {
    let mut a:usize = 0;
    let mut p:usize = 1;
    for i in 0..v.len(){
        a += v[i] * p;
        p *= 10;
    }
    return a;
}

//----------------
#[test]
fn test1(){    
    // assert_eq!(446,solve1(100));
    assert_eq!(8184200,solve1(1000000));
}

#[cfg(test)]
fn solve1(n:usize) -> usize {   
    let sieve = get_prime_sieve(n);
    let mut v:Vec<usize> = Vec::new();
    for i in 0..n {
        if sieve[i] && is_all_prime(i, &sieve) {v.push(i);}
    }    
    return v.into_iter().sum(); 
}

//---------------------
#[test]
fn test2(){    
    // assert_eq!(446,solve2(100));
    assert_eq!(8184200,solve2(1000000));
}

#[cfg(test)]
fn solve2(n:usize) -> usize {   
    let sieve = get_prime_sieve(n);
    let mut v:Vec<usize> = Vec::new();
    for i in 0..n {
        if sieve[i] && is_all_prime2(i, &sieve) {v.push(i);}
    }    
    return v.into_iter().sum(); 
}

#[cfg(test)]
fn is_all_prime2(a:usize, sieve:&Vec<bool>) -> bool {
    let ditit_a:Vec<usize> = to_digit(a);
    if a > 2 && contains_even(&ditit_a) {return false;}

    //get all permutation except own number
    let all_permu:Vec<Vec<usize>> = get_permu(&ditit_a);
    for v in all_permu{
        let num = to_num(&v);
        if num > sieve.len() || !sieve[num] {return false;}
    }
    return true;
}

#[cfg(test)]
fn contains_even(v:&Vec<usize>) -> bool {
    for i in v {
        if i % 2 == 0 {return true;}
    }
    return false;
}

 

끝