[Project Euler] 27. 연속되는 n에 대해 가장 많은 소수를 만들어내는 2차식 구하기

27. 연속되는 n에 대해 가장 많은 소수를 만들어내는 2차식 구하기

오일러는 다음과 같은 멋진 2차식을 제시했습니다.

n² + n + 41
이 식의 n에다 0부터 39 사이의 숫자를 넣으면, 그 결과는 모두 소수가 됩니다.
하지만 n = 40일 때의 값 40² + 40 + 41 은 40×(40 + 1) + 41 이므로 41로 나누어지고, n = 41일 때 역시 412 + 41 + 41 이므로 소수가 아닙니다.

컴퓨터의 발전에 힘입어 n² − 79n + 1601 이라는 엄청난 2차식이 발견되었는데, 이것은 n이 0에서 79 사이일 때 모두 80개의 소수를 만들어냅니다. 이 식의 계수의 곱은 -79 × 1601 = -126479가 됩니다.

아래와 같은 모양의 2차식이 있다고 가정했을 때,

n² + an + b   (단 | a | < 1000, | b | < 1000)
0부터 시작하는 연속된 n에 대해 가장 많은 소수를 만들어내는 2차식을 찾아서, 그 계수 a와 b의 곱을 구하세요.

Click

고민을 좀 많이 했습니다. 다른 분들 푸신것도 좀 보고...
http://blog.mycila.com/2009/05/project-euler-problem-27.html 에서는 어떻게 푸는 방법을 잘 정리해 놓은 것 같은데 영어와 공식의 압박에 제대로 이해를 못했네요. 아무튼 이용 할 수 있는 편법은 모두 이용해 봤습니다.

공식(n² + an + b)에 의해.
n = 0 -> b -> b는 소수.
n = 1 -> a + b + 1 -> a+b=1 or a+b=짝수(a,b 모두 홀수 or 모두 짝수)
n = 2 -> 2(a+2) + b -> b는 홀수 or (a=-2) 

(n=1)일때와 (n=2)일때를 종합하면.. a,b 모두 홀수 or a=-2,b=3(n=3일때

a <= -b & n = 1 -> 1보다 작은 값. -> a는 -b보다 큰 값.
n = b -> b(b + a + 1) 즉 최대 n<b.

 이전에 구한 max 보다 클려면 적어도 n = max+1일 때 값이 소수여야함.

그리고 매번 소수인지 판단하는 것은 너무 시간이 걸릴것이므로....
최대값 (실제론 여기까지 오지는 않을것 같지만) max*(2*max+1)까지의 소수여부를 미리 구했습니다.
소수 판단하는 것은 이전에 사용했던 에라토스테네스의 체를 이용했습니다.

<script language="Javascript" type="text/javascript">
function eratos(max){
 /* 2부터 n까지 n-1개를 저장할 수 있는 배열 할당
  * 배열 참조 번호와 소수와 일치하도록 배열의 크기는
  * n+1 길이만큼 할당(인덱스 번호 0과 1은 사용하지 않음)       */
 var PrimeArray = new Array();

 /* 배열초기화
  * 처음엔 모두 소수로 보고 true값을 줌  */
 PrimeArray[0] = PrimeArray[1] = false;
 for(var i=2; i<max; i++) PrimeArray[i]=true;

 /* 에라토스테네스의 체에 맞게 소수를 구함
  * 만일, PrimeArray[i]가 true이면 i 이후의 i 배수는
  * 약수로 i를 가지고 있는 것이 되므로 i 이후의 i 배수에 대해
  * false값을 준다.
  * PrimeArray[i]가 false이면 i는 이미 소수가 아니므로 i의 배수 역시
  * 소수가 아니게 된다. 그러므로 검사할 필요 없다. */
 for(var i=2; i*i<=max; i++)
  if(PrimeArray[i])
   for(var j=2*i; j<=max; j+=i)PrimeArray[j]=false;
 
 return PrimeArray;
}
</script>

그리고 아래가 이번에 구현한 코드입니다.

<script language="Javascript" type="text/javascript">
/* 2차식의 값. */
function func27(a,b,n){
    return r = n*n + a*n + b;
}
/* 연속되는 n에 대해 가장 많은 소수를 만들어내는 2차식의 a와 b의 곱. */
function p027(l){
    var prime = eratos(l*(2*l+1));  //에라토스테네스의 체로 소수배열 구함.
    
    var maxn = 0;
    var maxa = 0;
    var maxb = 0;
    for(var b=3; b<l; b+=2){        //b는 홀수.
        if(!prime[b])                //b는 소수.
            continue;
        for(var a=-b+2; a<l; a+=2){     //a는 -b보다 큰 홀수
            if(prime[func27(a,b,maxn+1)]){  //n = maxn+1 일때 값이 소수이면.
                var n=1;
                for(;n<=maxn; n++){         //0<n<maxn 일때 값이 소수인지 확인.
                    if(!prime[func27(a,b,n)])
                        break;
                }
                if(n>maxn){        
                    for(n=maxn+1; n<b; n++){         //새로운 maxn을 구함.
                        if(!prime[func27(a,b,n+1)])
                            break;
                    }
                    maxn = n;
                    maxa = a;
                    maxb = b;
                }
            }
        }            
    }
    return maxa*maxb;
}
</script>