[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>