[Project Euler] 49. 세 항이 소수이면서 다른 수의 순열이 되는 4자리 숫자의 등차수열 찾기

49. 세 항이 소수이면서 다른 수의 순열이 되는 4자리 숫자의 등차수열 찾기

1487, 4817, 8147은 3330씩 늘어나는 등차수열입니다. 이 수열에는 특이한 점이 두 가지 있습니다.

• 세 수는 모두 소수입니다.
• 세 수는 각각 다른 수의 자릿수를 바꿔서 만들 수 있는 순열(permutation)입니다.

1자리, 2자리, 3자리의 소수 중에서는 위와 같은 성질을 갖는 수열이 존재하지 않습니다. 하지만 4자리라면 위엣것 말고도 또 다른 수열이 존재합니다.

그 수열의 세 항을 이었을 때 만들어지는 12자리 숫자는 무엇입니까?

Click

에라스토테네스의 체를 이용 소수리스트를 구해 놓은 후, 1001부터 9999까지의 소수 i에 대해 i보다 큰 j와 i와 j사이의 차이만큼 j에 더한 값 k가 소수인지 확인을 하고, 세 수가 모두 소수이면, 세 수가 순열인지를 확인하였습니다.

<script language="Javascript" type="text/javascript">
/* 순열 판단 */
function isPermutation(num1, num2){
    var d = [0,0,0,0,0,0,0,0,0,0];
    for(var i=num1; i>=1; i/=10)
        d[~~(i%10)] ++;
    for(var j=num2; j>=1; j/=10)
        if((--d[~~(j%10)]) < 0)
            return false;
    
    return true;
}
/* 소수 리스트 */
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=4; i<=max; i+=2)PrimeArray[i]=false;
    for(var i=6; i<=max; i+=3)PrimeArray[i]=false;
    for(var i=5; i*i<=max; i+=6){
 if(PrimeArray[i]) for(var j=2*i; j<=max; j+=i)PrimeArray[j]=false;
        if(PrimeArray[i+2]) for(var j=2*(i+2); j+2<=max; j+=i+2)PrimeArray[j]=false;
    }
 
    return PrimeArray;
}
function p049(){
    var prime = eratos(10000);
    var r= new Array();
    for(var i=1001; i<10000; i+=(i%6==1)?4:2){
        if(prime[i]){
            var lim = i + (100000-i)/2;
            for(var j=i+((i%6==1)?4:2); j< lim;j+=(j%6==1)?4:2){
                var k = j+(j-i);
                if(prime[j] && prime[k])
                    if(isPermutation(i,j) && isPermutation(i,k))// && i != 1487)
                        r[r.length] = i*100000000 + j*10000 + k;
            }
        }
    }
    
    alert(r);
}
</script>