[Project Euler] 51. 일부 숫자를 치환했을 때 8개의 서로 다른 소수가 생기는 가장 작은 소수

51. 일부 숫자를 치환했을 때 8개의 서로 다른 소수가 생기는 가장 작은 소수

두 자리 숫자 *3의 첫번째 자리를 여러가지로 바꿨을 때 가능한 아홉 가지의 결과 중에서 13, 23, 43, 53, 73, 83의 여섯 개는 소수입니다.

56**3 의 3번째와 4번째 자리를 동일한 숫자로 바꿔서 만들어지는 10개의 다섯자리 숫자 중에서는 아래에서 보듯이 7개가 소수가 되며, 이것은 이런 식으로 7개의 소수가 만들어지는 첫번째 경우입니다. 이 소수 집단의 첫번째 수인 56003은 이런 성질을 갖는 가장 작은 소수입니다.

56003, 56113, 56333, 56443, 56663, 56773, 56993
위의 예처럼 원래의 일부를 동일한 숫자로 치환했을 때 8개의 소수 집단이 만들어지는 경우를 찾고, 그 집단에 속한 가장 작은 소수를 구하세요.
치환하는 자리는 인접하지 않아도 되고, 가장 앞부분을 치환하는 경우 거기에 0은 올 수 없습니다.

Click
http://nianelo4.blog.me/ 블로그의 동일 문제 풀이에 대해 참고.

1. 마지막 자리에 짝수나 5가 올 경우 2의 배수 혹은 5의 배수이므로 마지막 자리에 올 수 있는 수는 1,3,7,9가 전부.
2. 반복되는 수의 갯수는 3의 배수개일 때만 가능하다.
3의 배수 판단법으로 각 자리의 수를 모두 더했을 때 3의 배수가 되는 수를 찾는 방법을 이용.
반복 되는 수가 3의 배수가 아닐때 각 자릿수를 더한 값은 3번의 한번 3의 배수가 된다.
즉 반복되는 수가 3의 배수이고, 그 외의 자릿수들의 합이 3의 배수가 아닐때 만 8개 이상의 값이 나올 수 있다.

알고리즘은 해당 블로그와 다르네요.

일단 각 자릿수마다 사용하는 패턴이 다르므로 자릿수 증가시마다 패턴을 새로 구합니다.
각 패턴과 i값에 대해 고정 값 n을 만듭니다.
고정값 n에 패턴 * k 를 더해가며 만들어지는 수에 대해 소수인지를 판단하고 최종적으로 소수의 수를 구합니다.
가장 작은 값을 구하는 것이므로 min값이 나온 자릿수보다 자릿수 증가가 일어나기 전까지 연산을 해봅니다.

<script language="Javascript" type="text/javascript">
/* 소수 판단. */
function isPrime(n){
 if(n < 2) return false;
 else if(n < 4) return true;
 else if(n%2 == 0 || n%3 == 0) return false;

 for(var i=5; i*i<=n; i+=6)
     if(n%i == 0 || n%(i+2) == 0)
         return false;
 
 return true;
}
//t와 f의 수의 따라 가능한 패턴을 얻는다.
function get051Patterns(t,f,patterns,tn,fn){
    if(t==tn && f==fn)
        return [patterns];
    
    var r = [];
    if(fn < f)
        r = get051Patterns(t, f, patterns*10, tn, fn+1);
    if(tn < t){
        var temp = get051Patterns(t, f, patterns*10+1, tn+1, fn);
        for(var i in temp)
            r[r.length] = temp[i];
    }
    return r;
}
function p051(){
    var pn = 3, goal = 8;   //기본 변수 설정.
    var digit = 0, ten = 1, patterns, min = Number.MAX_VALUE, minDig = 100;
    for(var i=1; ; i+=(i%10==3)?4:2){
        //자릿수 증가시 새로운 패턴을 얻음.
        if(i >= ten){
            if(minDig == digit)
                break;
            patterns = get051Patterns(pn, digit++, 0, 0, 0);
            ten *= 10;
        }
        
        for(var j in patterns){
            //패턴과 i값을 이용해 고정 값 n을 얻음.
            var cnt = 0;
            var pattern = patterns[j] * 10;
            var n = i;
            for(var k=1; k < pattern; k*=10)
                if(~~(pattern/k)%10 == 1)
                    n = (parseInt(n/k))*k*10 + n%k;
            
            //고정값에 패턴값을 더해가며 소수를 찾음.
            var t = Number.MAX_VALUE;
            for(var k=(pattern < ten * Math.pow(10, pn-1))?0:1; goal<11-k+cnt; k++){
                if(isPrime(n + pattern*k)){
                    if(n+pattern*k < t){
                        t = n+pattern*k;
                        if(t > min)
                            break;
                    }
                    cnt ++;
                }
            }
            
            //소수의 수를 파악하여 결과값을 구함.
            if(cnt >= goal){
                if(min>t){
                    min = t;
                    minDig = digit;
                }
            }
        }
    }
    
    alert(min);
}
</script>

탐색 시간 0.02초 정도.