[Project Euler] 50. 1백만 이하의 소수 중 가장 길게 연속되는 소수의 합으로 표현되는 수는?

50. 1백만 이하의 소수 중 가장 길게 연속되는 소수의 합으로 표현되는 수는?

41은 소수이면서 다음과 같은 6개의 연속된 소수의 합으로도 나타낼 수 있습니다.

41 = 2 + 3 + 5 + 7 + 11 + 13

이것은 100 이하에서는 가장 길게 연속된 소수의 합으로 이루어진 소수입니다.

1000 이하에서는 953이 연속된 소수 21개의 합으로 가장 깁니다.

1백만 이하에서는 어떤 소수가 가장 길게 연속되는 소수의 합으로 표현될 수 있습니까?

Click

prime[n] = n 번째 소수.
sum[n][m] = n번째 소수부터 m번째 소수까지를 모두 더한 수
                    (prime[n] + prime[n+1] + ....... + prime[m-1] + prime[m])

라고 할때.

sum[n][m] = 0번째 소수부터 m번째 소수를 더한 수 - 0번째 소수부터 n번째 소수를 더한 수
                     (sum[0][m] - sum[0][n])

가 된다.

에라스토테네스의 체로 소수를 모두 구한 후,
소수들을 체크해나가며 소수들을 더해가 0번째 소수(2)부터 n번째 소수까지의 합 sum[n]의 배열을 채우고, 동시에 sum[n]이 소수인지를 체크해 소수가 되는 sum[n]을 찾아 '첫번째 소수부터 시작하는 가장 길게 연속되는 소수의 합' 을 구한다.

이후 i는 1부터 증가시켜가고, j는 sum.length 부터 감소시켜가며 sum[j] - sum[i]가 소수가 되는 수를 찾아 'i번째 소수부터 시작하는 가장 길게 연속되는 소수의 합'을 구한다.

이때 max count보다 작은 값을 갖는 범위는 탐색할 필요가 없으므로
i값은 sum.length - i 가 max conut 보다 클때만 탐색하고,
j값은 j - i 가 max count 보다 클때만 탐색하면 된다.

<script language="Javascript" type="text/javascript">
/* 에라스토테네스의 체 */
function eratos(max){
    var PrimeArray = new Array();

    PrimeArray[0] = PrimeArray[1] = false;
    for(var i=2; i< max; i++) PrimeArray[i]=true;

    for(var i=4; i<=max; i+=2)PrimeArray[i]=false;
    for(var i=6; i<=max; i+=3)PrimeArray[i]=false;
    for(var i=5; i*i<=max; i+=6){
 if(PrimeArray[i]) for(var j=2*i; j<=max; j+=i)PrimeArray[j]=false;
 if(PrimeArray[i+2]) for(var j=2*(i+2); j+2<=max; j+=i+2)PrimeArray[j]=false;
    }

    return PrimeArray;
}
function p050(limit){
    //소수 판별 배열.
    var check = eratos(limit);
    
    //첫번째 소수부터 시작하는 가장 길게 연속되는 소수의 합.
    var sum = []; sum[0] = 2; sum[1] = 2 + 3;
    var max = 2, r = 5;
    for(var i=5; sum[sum.length-1]<=limit; i+=(i%6==1)?4:2){
        if(check[i]){
            sum[sum.length] = sum[sum.length-1] + i; //0 ~ n번째 소수까지의 합.
            if(check[sum[sum.length-1]]){
                max = sum.length;
                r = sum[sum.length-1];
            }
        }
    }
    
    //i번째 소수부터 시작하는 가장 길게 연속되는 소수의 합.
    for(var i=1; sum.length-i>max; i++){
        for(var j=sum.length; j-i>=max; j--){
            var temp = sum[j] - sum[i]; //j ~ i번째 소수까지의 합.
            if(check[temp]){
                max = j-i+1;
                r = temp;
            }
        }
    }

    alert(r);
}
</script>

탐색시간 0.85(s)