< 목차 >


9/6 프로그래머스 lv.1 소수 만들기

문제 설명


프로그래머스 lv.1 소수 구하기

<aside> ✏️ 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return하도록 한다.

</aside>

에라토스테네스의 체


소수를 찾는 가장 일반적인 방법!

<에라토스테네스의 체> 방식으로 소수 찾기

<에라토스테네스의 체> 방식으로 소수 찾기

  1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열합니다.(그림에서 회색 사각형)
  2. 2는 소수이므로 오른쪽에 2를 씁니다. 자기 자신을 제외한 2의 배수를 모두 지웁니다.
  3. 남아 있는 수 가운데 3은 소수이므로 오른쪽에 3을 씁니다. 자기 자신을 제외한 3의 배수를 모두 지웁니다.
  4. 남아 있는 수 가운데 5는 소수이므로 오른쪽에 5를 씁니다. 자기 자신을 제외한 5의 배수를 모두 지웁니다.
  5. 남아 있는 수 가운데 7은 소수이므로 오른쪽에 7을 씁니다. 자기 자신을 제외한 7의 배수를 모두 지웁니다.
  6. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남습니다.

이 이미지의 경우 120까지의 소수를 구하는 모습을 보여주고 있는데, $10^2<120<11^2$이므로 10보다 작거나 같은 소수. 즉, 2, 3, 5, 7의 배수들만 지우면 됩니다.