소수
약수가 1과 자기 자신밖에 존재하지 않는 수
대표적인 판별법
에라토스테네스의 체
- 구하고자 하는 소수의 범위만큼 1차원 배열을 생성
- 2부터 작하고 현재 숫자가 지워지지 않을 때는 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하면서 지움
- 배열의 긑까지 2를 반복한 후 배열에서 남아있는 모든 수를 출력
example
1은 소수가 아니기 때문에 2부터 시작합니다.
2는 소수입니다. 2의 배수를 모두 삭제합니다.
3은 지워지지 않았습니다. 3을 선택하고 3의 배수를 모두 삭제합니다.
5는 지워지지 않았습니다. 5를 선택하고 5의 배수를 모두 삭제합니다.
7은 지워지지 않았습니다. 7을 선택하고 7의 배수를 모두 삭제합니다.
다음과 같이 알고리즘을 만들면 해당 범위내의 소수를 구할 수 있습니다.
