[Project Euler] 37. 왼쪽이나 오른쪽에서 한자리씩 없애가도 여전히 소수인 수의 합은?

37. 왼쪽이나 오른쪽에서 한자리씩 없애가도 여전히 소수인 수의 합은?

소수 3797에는 왼쪽부터 자리수를 하나씩 없애거나 (3797, 797, 97, 7) 오른쪽부터 없애도 (3797, 379, 37, 3) 모두 소수가 되는 성질이 있습니다.

이런 성질을 가진 소수는 단 11개만이 존재합니다. 이것을 모두 찾아서 합을 구하세요.

(참고: 2, 3, 5, 7은 제외합니다)

Click
개인적으로 별로 좋아하는 스타일의 문제는 아니군요. 11개라는 값을 모른다면 무한 탐색을 해야하는 문제고... 무엇보다 무한한 소수중에서 11개라고 딱 정의 내릴 수 있는게 어떻게 가능한지...... 일단 문제를 냈으니 11개는 맞을테지만 그 한계치를 정한 방법이 궁금...

일단 주어진 한계값은 11개밖에 없다는 점 하나군요. 그래서 최대치는 count를 해가며 count값이 11이면 종료하도록 설계.

한계값이 정해져 있다면 에라토스의 체로 모든 소수를 구해 놓은 다음에 그 안에서 판별하는 것도 좋은 방법이겠으나, 한계값이 없으므로 정석대로 brute-force 로 구했습니다.

시작점은 1의 자리가 아니고, 10대의 수 또한 1만 남으면 소수가 아니기 때문에 21부터 시작 짝수는 판단 안해도 되니 2씩 증가.

오른쪽, 왼쪽 부터 지워주는 방법은..

왼쪽부터 지우는 방법은 나누기 10을 해주면 되고..
오른쪽부터 지우는 방법은 생각을 달리해 %10^n씩 해주며 왼쪽부터 쓰는것으로... 역으로 처리하였습니다.

<script language="Javascript" type="text/javascript">
/** 소수 판단. 
 * @param {Object} n : 판별하고자 하는 수.
 * @return {Array} : true, false.
 **/
function isPrime(n){
 if(n <= 1) return false;
 if(n == 2) return true;
 else if(n%2 == 0)
  return false;
 
 for(var i=3; i*i<=n; i+=2){
     if(n%i == 0)
         return false;
 }
 return true;
}
function p037(){
    var cnt = 0;
    var sum = 0;
    for(var i=21; cnt<11; i+=2){
        if(isPrime(i)){
            var temp1 = i%10;
            var temp2 = parseInt(i/10);
            var check = true;
            for(var j=2; temp1 < i; j++){
                if(!isPrime(temp1) || !isPrime(temp2)){
                    check = false;
                    break;
                }
                temp1 = i % Math.pow(10, j);
                temp2 = parseInt(temp2/10);
            }
            if(check){
                sum += i;
                cnt ++
            }
        }
    }
    alert(sum);
}
</script>

그런데 답을 구해놓고 보니 답글란에 첫번째 자리(가장 좌측)에 올 수 있는 수는 {2,3,5,7} 뿐이고... 중간에 들어갈 수 있는 수는 {1,3,7,9} (짝수와 5의 배수를 만들 수 있는 수 제외) 뿐
이라는 댓글을 보고 해당 성질을 이용하면 좀 더 효율적으로 구할 수 있을 것 같아서 위에 두 성질에 1의 자리(가장 오른쪽)에는 {3,7}만 가능 하다는 성질을 더해서 새로 구현해 봤습니다.

첫번째 들어 갈 수 있는 수 {2, 3, 5, 7} => 혼자 남았을때 소수가 되는 수.
가운데 들어 갈 수 있는 수 {1, 3, 7, 9} => 1의 자리에 남았을 때 짝수나 5의 배수를 만들지 않는 수.
마지막에 들어 갈 수 있는 수 {3, 7} => 혼자 남았을 때 소수가 되며, 짝수와 5의 배수를 만들 수 없는 수

<script language="Javascript" type="text/javascript">
/** 소수 판단. 
 * @param {Object} n : 판별하고자 하는 수.
 * @return {Array} : true, false.
 **/
function isPrime(n){
 if(n <= 1) return false;
 if(n == 2) return true;
 else if(n%2 == 0)
  return false;
 
 for(var i=3; i*i<=n; i+=2){
     if(n%i == 0)
         return false;
 }
 return true;
}
function p037(){
    /* 첫, 중간, 마지막자리에 올 수 있는 값. */
    var fn = new Array(2,3,5,7);  //첫번째(가장 왼쪽) 올 수 있는 값.
    var mn = new Array(1,3,7,9);  //중간에 올 수 있는 값.
    var ln = new Array(3,7);      //마지막(가장 오른쪽) 올 수 있는 값.
    
    /* 각 자리수 탐색 위치 초기 설정. */
    var p = new Array();
    p[0] = 0;
    p[1] = 0;
    
    /* 변수 초기화. */
    var cnt = 0;
    var sum = 0;
    
    while(cnt<11){
        /* n값 구하기. */
        var n = fn[p[p.length-1]];
        for(var i=p.length-2; i>0; i--){
            n = n*10 + mn[p[i]]
        }
        n = n*10 + ln[p[0]];
        
        /* n이 소수일경우. */
        if(isPrime(n)){
            var temp1 = n%10;           //우측부터 씀.(좌측부터지우는걸 역으로)
            var temp2 = parseInt(n/10); //우측부터 지움.
            var check = true;
            for(var j=2; temp1 < n; j++){
                if(!isPrime(temp1) || !isPrime(temp2)){
                    check = false;
                    break;
                }
                temp1 = n % Math.pow(10, j);
                temp2 = parseInt(temp2/10);
            }
            if(check){
                sum += n;
                cnt ++
            }
        }
        
        /* 다음 자릿수 탐색 위치를 찾음. */
        p[0] ++;
        if(p[0] >= 2){
            p[0] = 0;
            p[1] ++;
            for(var i=1; i< p.length; i++){
                if(p[i] >= 4){
                    p[i] = 0;
                    if(i==p.length-1)
                        p[i+1] = 0;
                    else
                        p[i+1] ++;
                }
                else
                    break;
            }
        }
    }
    
    //결과값.
    alert(sum);
}
</script>