35. 프로젝트 오일러 #35 : 순환하는 소수들

197과 같은 소수는 한자리씩 순환하여도, 계속 소수가 됩니다.  197도 소수이지만, 971, 719도 소수가 되는 것이죠.

이 문제는 이러한 소수들을 찾는 것인데, 결국 한계값까지 소수들을 구한 후, 자릿수 순환해서 소수인지 검사하면 됩니다.  그래서인지 난이도도 5%네요.

프로그램은 아주 간단합니다.  한계값까지 모든 소수를 구한 후에 각각의 소수들에 대해서 순환 여부를 판단하면 됩니다.

뭐 그냥 짜도 되겠지만, 제 경우에는 배열에 소수값을 넣지 않고 플래그처럼 사용해서 프로그램을 짰습니다.  2는 예외이고요.  어차피 유일한 짝수 소수이니까요.  예외 처리를 해도 무방합니다.  그리고 모든 자릿수가 홀수여야 하겠죠.  2를 제외하고는 짝수가 들어가서는 절대 순환하는 수들이 소수가 될 수 없으니까요.

제가 작성한 프로그램은 다음과 같습니다.

소스는 참고용으로만 봐주세요.

#include <stdio.h>

unsigned char primes[1000000/2];

int main()
{
    int ans = 1;
    int n = 1000000;
    for( int i = 3 ; i < n ; i+=2 )
    {
        if( primes[i/2] ) continue;
        for( int j = i+i+i ; j < n ; j += i+i ) primes[j/2] = 1;
    }
    int digit = 1, k = 0;
    for( int i = 3 ; i < n ; i+=2 )
    {
        if( primes[i/2] ) continue;
        if( i > digit*10 ) { digit *= 10; k++; }
        bool flag = true;
        for( int j = 0, s = i ; j < k ; j++ )
        {
            int last = s%10;
            s /= 10;
            s += digit*last;
            if( s%2 == 0 || primes[s/2] ) { flag = false; break; }
        }
        if( flag ) ans++;
    }
    printf("Ans = %d\n", ans);
}