< 목차 >
9/6 프로그래머스 lv.1 소수 만들기
문제 설명
프로그래머스 lv.1 소수 구하기
<aside>
✏️ 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return하도록 한다.
</aside>
에라토스테네스의 체
소수를 찾는 가장 일반적인 방법!

<에라토스테네스의 체> 방식으로 소수 찾기
- 2부터 소수를 구하고자 하는 구간의 모든 수를 나열합니다.(그림에서 회색 사각형)
- 2는 소수이므로 오른쪽에 2를 씁니다. 자기 자신을 제외한 2의 배수를 모두 지웁니다.
- 남아 있는 수 가운데 3은 소수이므로 오른쪽에 3을 씁니다. 자기 자신을 제외한 3의 배수를 모두 지웁니다.
- 남아 있는 수 가운데 5는 소수이므로 오른쪽에 5를 씁니다. 자기 자신을 제외한 5의 배수를 모두 지웁니다.
- 남아 있는 수 가운데 7은 소수이므로 오른쪽에 7을 씁니다. 자기 자신을 제외한 7의 배수를 모두 지웁니다.
- 위의 과정을 반복하면 구하는 구간의 모든 소수가 남습니다.
이 이미지의 경우 120까지의 소수를 구하는 모습을 보여주고 있는데, $10^2<120<11^2$이므로 10보다 작거나 같은 소수. 즉, 2, 3, 5, 7의 배수들만 지우면 됩니다.