Script / CSS

G1sUtil.js

G1sBlogger.js

G1sNavigationList.js

G1sCode

Posts List


2012년 4월 10일 화요일

[Project Euler] 41. n자리 팬디지털 소수 중에서 가장 큰 수

41. n자리 팬디지털 소수 중에서 가장 큰 수
1부터 n까지의 숫자를 하나씩만 써서 만든 n자리 숫자를 팬디지털(pandigital)이라고 부릅니다. 2143은 4자리 팬디지털인데, 이 수는 동시에 소수이기도 합니다.

 n자리 팬디지털 소수 중에서 가장 큰 수는 무엇입니까?
Click
가장 큰 수이므로 n=9에서부터 시작하여 큰 수부터 작은수 순으로 팬디지털을 만들어가며 가장 먼저 발견되는 소수를 찾았습니다.

 여기에 모든 각 자릿 수를 더한 값이 3의 배수가 나오면 해당 수는 3의 배수이므로 판단에서 제외 할 수 있습니다. (n=9,8,6,5,3,2 제외)
<script language="Javascript" type="text/javascript">
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 func041(nums, num, digit, n){
    if(digit == n){
        if(isPrime(num))
            return num;
        else 
            return 0;
    }
    for(var i=n; i>0; i--){
        if(nums[i]){
            nums[i] = false;
            var r = func041(nums,num*10+i,digit+1,n);
            if(r != 0)
                return r;
            nums[i] = true;
        }
    }
    return 0;
}
function p041(){
    var max = 0, nums = [false,true,true,true,true,true,true,true,true,true];
    
    for(var n=9; n>0; n--){
        if(parseInt((n+1)*n/2) % 3 == 0)
            continue;
        max = func041(nums, 0, 0, n);
        if(max != 0)
            break;
    }
    alert(max);
}
</script>

댓글 2개:

  1. 이 문제는, 풀던 당시에는 몰랐는데
    4자리수와 7자리수만 가능한거였군요 ㅋㅋ

    조금만 더 계산해봤으면 알아챌만한 것이었는데 ^^;

    답글삭제
    답글
    1. 네. 3의 배수 판단으로 꽤 많이 걸러낼 수 있는 문제였네요. ^^

      삭제