소수 (Prime Number) : 자신보다 작은 2개의 자연수를 곱해 만들 수 없는 1보다 큰 자연수를 말합니다.

1과 자기 자신 외에 약수가 존재하지 않는 수를 말합니다.

소수 구하기의 핵심 이론

에라토스테네스의 체 원리

1. 구하고자 하는 소수의 범위만큼 1차원 배열을 생성합니다.
2. 2부터 시작하고 현재 숫자가 지워지지 않을 때는 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하면서 지웁니다. 이때 처음으로 선택된 숫자는 지우지 않습니다.
3. 배열의 끝까지 2를 반복한 후 배열에서 남아 있는 모든 수를 출력합니다.

에라토스테네스의 체를 사용할 때 시간 복잡도는?

• 일반적으로는 에라토스테네스의 체를 구현하려면 이중 for문을 이용하므로 시간 복잡도가 O(n^2)정도라고 판단할 수 있다.
• 하지만 실제 시간 복잡도는 최적화의 정도에 따라 다르지만, 일반적으로는 O(Nlog(logN))이다.