소수 판별 2

1. 문제

 

2. 입출력

 

3. 입출력 예시

 

4. 문제 설계

특정 수가 소수인지 판별하는 방법은 제곱근까지 나누어 떨어지는 것이 있는 지 판단하는 방법이 빠르지만,

특정 범위 내에 모든 소수를 구하는 방법은 에라토스테네스의 체 알고리즘으로 시간복잡도 O(NlogN)으로 해결할 수 있음.

에라토스테네스의 체 알고리즘은 2부터 특정 범위까지 배수를 모두 지워 남은 수가 특정 범위 내의 소수임을 알 수 있음.

 

5. 전체 코드

 

전체코드는 여기에서 확인할 수 있습니다.