콘텐츠로 건너뛰기
Home » 10001번째소수

10001번째소수

오일러 프로젝트 07

오일러 프로젝트 7번문제는 10001번째 소수를 찾는 문제이다.

소수를 크기 순으로 나열하면 2, 3, 5, 7, 11, 13, … 과 같이 됩니다. 이 때 10,001번째의 소수를 구하세요.(http://euler.synap.co.kr/prob_detail.php?id=7)

오일러 프로젝트에서 처음으로 소수 판별 함수를 작성해볼 차례이다. 소수 판별 함수는 사실 알고리듬 자체는 매우 단순한데, 문제는 성능이다. 나이브하게 작성한 코드는 매우 느릴 수 밖에 없다.

  1. 2보다 작은 수는 0, 1 외에 음수이므로 이들은 모두 소수가 아니다.
  2. 2는 소수이다.
  3. 2보다 큰 경우 2, 3, 4… 등 자기 자신보다 작은 수로 나눠서 한 번이라도 나눠지면 소수가 아니다.
  4. 그 외에는 소수이다.

더 보기 »오일러 프로젝트 07