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