[Project Euler] 35. 백만 이하인 circular prime 개수 구하기

35. 백만 이하인 circular prime 개수 구하기

소수 중에서 각 자리의 숫자들을 순환시켜도 여전히 소수인 것을 circular prime이라고 합니다. 예를 들어 197은 971, 719가 모두 소수이므로 여기에 해당합니다.

이런 소수는 100 밑으로 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97 처럼 13개가 있습니다.

그러면 1,000,000 밑으로는 모두 몇 개나 있을까요?

Click
에라토스의 체로 소수 리스트를 구한 후 소수를 해당 자릿수만큼 돌며 수를 순환시켜 circular prime인지를 판단하였습니다.

<script language="Javascript" type="text/javascript">
//에라토스의 체 - 소수판단.
function eratos(max)
{
 var PrimeArray = new Array();

 PrimeArray[0] = PrimeArray[1] = false;
 for(var i=2; i< max; i++) PrimeArray[i]=true;

 for(var i=2; i*i<=max; i++)
  if(PrimeArray[i])
   for(var j=2*i; j<=max; j+=i)PrimeArray[j]=false;
 
 return PrimeArray;
}
function p035(max){
    prime = eratos(max);
    
    //소수 중에 수를 순환시켜 circular prime를 구한다.
    var cnt = 1;        //2
    for(i=3; i< max; i+=2){
        if(prime[i]){
            var temp = i;
            var digit = Math.ceil(Math.log(temp)/Math.log(10));  //자릿수
            for(var j=0; j< digit; j++){
                //수를 순환시킴
                temp = (temp%10)*Math.pow(10,digit-1) + parseInt(temp/10);  
                if(!prime[temp])
                    break;
            }
            if(j == digit)
                cnt ++;
        }
    }
    alert(cnt);
}
</script>

해당 답글란에 10보다 큰 수는 1,3,7,9로만 이루어진 것만 판단하면 비교횟수를 크게 줄일 수 있다고 하시네요.
그 외에 숫자가 들어오면 순환수 중에 짝수로 끝나거나 5의 배수로 끝나는 수가 나온다고....

좋은 방법이긴 하나 일단 해당 방법도 일일이 소수 판단을 하는 것보단 에라토스의 체로 소수리스트를 하나 구해놓고 하는게 효율면에서 더 좋을 것 같구요.
숫자를 돌며 해당수가 1,3,7,9만으로 이루어진 수인지를 판단하는 방법은 에라토스체를 구한상태에서 소수 판단하는 것보다 오래 걸릴 것 같고....

따로 1,3,7,9로만 이루어진 리스트를 구해서 하는 방법은 좀 더 효율을 높일 수 있을 것 같네요.