10 이하의 소수를 모두 더하면 2 + 3 + 5 + 7 = 17 이 됩니다.
이백만(2,000,000) 이하 소수의 합은 얼마입니까?
Click이백만(2,000,000) 이하 소수의 합은 얼마입니까?
원래는 처음과 마찬가지로 소수를 배열에 저장해가며 해당 수로 나눠줘 소수를 판단 하였으나 이게 각 수마다 나눠줘야하므로 많은 시간이 걸리는데, 문제를 풀고나서 댓글에 나온 '에라토스테네스의 체'라는 알고리즘을 발견 하였네요.
우선은 처음 했던 코드입니다.
그리고 에라토스테네스의 체 알고리즘은....
위키백과 : 에라토스테네스의 체 |
- 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
- 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
- 자기 자신을 제외한 2의 배수를 모두 지운다.
- 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
- 자기 자신을 제외한 3의 배수를 모두 지운다.
- 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
- 자기 자신을 제외한 5의 배수를 모두 지운다.
- 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.
아무튼 이를 보고 약간 변형해서 구현.
<script> function sumEratos(max) { // 만일 n이 1보다 작거나 같으면 함수 종료 if(max<=1) return 0; /* 2부터 n까지 n-1개를 저장할 수 있는 배열 할당 * 배열 참조 번호와 소수와 일치하도록 배열의 크기는 * n+1 길이만큼 할당(인덱스 번호 0과 1은 사용하지 않음) */ var PrimeArray = new Array(); /* 배열초기화 * 처음엔 모두 소수로 보고 true값을 줌 */ for(var i=1; i<max/2; i++) PrimeArray[i]=true; /* 더한 값을 저장할 변수. */ var sum = 2; /* 에라토스테네스의 체에 맞게 소수를 구함 * 만일, PrimeArray[i]가 true이면 i 이후의 i 배수는 * 약수로 i를 가지고 있는 것이 되므로 i 이후의 i 배수에 대해 * false값을 준다. * PrimeArray[i]가 false이면 i는 이미 소수가 아니므로 i의 배수 역시 * 소수가 아니게 된다. 그러므로 검사할 필요도 없다. * * 짝수는 2 밖에 없으므로 2를 제외한 홀 수만 계산한다. * 2*i+1 값이 실제의 값이 됨.. * */ for(var i=1; i<max/2; i++){ if(PrimeArray[i]){ var p = 2*i+1; sum += p; for(var j=3; j*p<max; j+=2)PrimeArray[(j*p-1)/2]=false; } } return sum; } </script>
댓글 없음:
댓글 쓰기