오일러 프로젝트 7번
문제 소수를 크기 순으로 나열하면 2, 3, 5, 7, 11, 13, ... 과 같이 됩니다. 이 때, 10,001 번째의 소수를 구하세요. 풀이 드디어 소수 판별 함수가 등장할 차례이다. 소수의 목록을 구하는 방법에는 크게 두 가지 가 있는데, 하나는 소수판별함수를 작성하여 루프를 돌거나 리스트를 필터링하는 것이고 다른 하나는 에라토스테네스의 체를 이용하는 것이다. 에라토스테네스의 체는 매우 빠르게 동작할 수는 있지만 범위를 알고 있는 경우에 유용할 수 있다. 소수의 분포에는 현재까지는 알려진 규칙이 없으므로 10,001 번째 소수가 어디쯤에 위치할지를 가늠할 수 없다. 따라서 소수 판별 함수를 통해서 2에서부터 소수를 하나씩 세어보는 수 밖에 없을 것 같다. 관건은 얼마나 빠른 소수 판별 함수를 작성..
더보기