본문 바로가기

#71

7. 프로젝트 오일러 #7 : 10,001번째 소수 찾기 큰 수에 대한 소수를 찾는 것이라면, 응당 다른 방법을 택해야 하겠지만,비교적 작은 소수에 대해서는 에라스토테네스의 체 이상 가는 알고리즘이 별로 없습니다. 특히 이번 문제와 같이 10,0001번째 소수 찾기라면 더더욱 말이죠. 알고리즘 자체는 아주 간단합니다.소수를 저장할 수 있는 배열 공간을 잡고, 여기에 차곡차곡 소수를 담아넣습니다.일단 2를 제외한 모든 소수는 홀수이므로, 검사해야 하는 수를 절반으로 줄일 수 있습니다. 2를 제외한다면, 소수는 다음과 같이 표현될 수 있습니다.

2 k + 1

2와 3을 제외한다면, 소수는 다음과 같이 표현될 수 있습니다.

6 k \pm 1

2, 3, 5를 제외한다면, 소수는 다음과 같이 표현됩니다.\[ 30k + r ~where~ (30, r) =.. 2014. 12. 23.

이전 1 다음

728x90

티스토리툴바