소수(Prime Number) 구하기 - JAVA

소수는 2보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로 나누어 떨어지지 않는 자연수 입니다.

예를 들면 2, 3, 5, 7 등 다른 수로 나누어 질 수 없는 수입니다.

 

에라토스테네스의 체

---

소수를 구하는 대표적인 판별법은 에라토스테네스의 체가 있습니다. 

출처 : https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체를 이용해 소수를 구하는 방법은 다음과 같습니다.

1. 구하고자하는 소수의 범위 만큼 1차원 배열 생성
2. 2부터 시작하여 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하며 지움
3. 다음 숫자 중 지워지지 않은 숫자로 이동
4. 배열의 끝에 도달할 때까지 2~3번 반복

에라토스테네스의 체의 경우 이중 for문을 이용하지만 배수를 삭제하는 연산으로 인해 실제 구현에서 for문이 생략되는 경우가 빈번하게 발생합니다. 그렇기 때문에 O(nlog(logn))의 시간 복잡도가 나옵니다.