알고리즘 코딩테스트 핵심이론 강의 - 소수 구하기 (에라토스테네스의 체)

https://www.youtube.com/watch?v=R1vl8FNAC6Q&list=PLFgS-xIWwNVX-zm4m6suWC9d7Ua9z7fuT&index=25

📌 소수 구하기

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

◾ 에라토스테네스의 체 원리

• 구하고자 하는 소수의 범위만큼 1차원 배열을 생성
• 2부터 시작하고 현재 숫자가 지워지지 않을 때 현재 선택 된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색
  이때 처음으로 선택 된 숫자는 지우지 않는다. → 이 수가 소수이기 때문
• 배열의 끝까지 반복 한 후 남아있는 배열에서 남아있는 모든 수를 출력
• 이중 for문을 사용하므로 시간 복잡도가 O(N²)라고 생각 할 수 있으나 실제 시간 복잡도는 일반적으로 O(Nlog(logN)) 이다.

◾ 에라토스테네스의 체 수행과정

1. 주어진 범위까지 배열 생성. 1은 소수가 아니므로 삭제하고 배열은 2부터 시작

2. 선택한 수의 배수를 모두 삭제

• 현재 선택 한 수가 2이기 때문에 2의 배수를 모두 삭제

3. 지워지지 않은 수를 선택 한 후 선택한 수의 모든 배수를 삭제. 이미 삭제된 수는 다시 지우지 않는다.

4. 이 과정을 배열의 끝까지 반복

5. 삭제되지 않은 수를 모두 출력