[정수론] 소수

✔ 소수 구하기

소수란?

• 1과 자기 자신 외에 약수가 존재하지 않는 수

에라토스테네스의 체

• 소수를 구하는 대표적인 판별법
• 현재 코딩 테스트에서 소수를 구하는 일반적인 방법으로 통용
• 이중 for문을 사용하므로 시간 복잡도가 O(N²) 정도라고 판단할 수 있음
• 하지만 실제 시간 복잡도는 최적화의 정도에 따라 일반적으로 O(Nlog(logN))
• 배수를 삭제하는 연산으로 실제 구현에서 바깥쪽 for문을 생략하는 경우가 빈번하게 발생하기 때문

에라토스테네스의 체 원리

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

 

Do it! 알고리즘 코딩테스트 with JAVA

https://inf.run/w9Tn