소수 구하기

🤔 소수(Prime number) 란?

• 1과 자기 자신 외에 약수가 존재하지 않는 수를 의미한다.
• 시간 복잡도는 일반적으로 O(Nlog(logN)) 이다.
  이중 for문을 탐색하는 동안 시간 복잡도가 O(N^2)이 될 수도 있지만, 제거하는 연산으로 인해 실제 반복문에서 생략하는 경우의 수가 발생하기 때문에 O(Nlog(logN))의 시간 복잡도가 발생할 수 있다.

👉 소수 구하는 방법 (에라토스테네스의 체)

• 에라토스테네스의 체  원리
  1. 구하고자하는 소수 범위만큼 1차원 리스트를 생성한다.
  2. 2부터 시작해서 기준 소수 값을 선택하고, 1차원 리스트를 탐색한다.
  3. 만약, 탐색하는 숫자가 지워지지 않고, 기준 소수값의 배수에 해당한다면 해당 숫자를 지운다.
  4. 3번의 수행을 리스트 끝까지 반복해서 남아있는 수를 출력한다.

에라토스테네스의 체 원리

✔️ 에라토스테네스의 체 과정

1. 주어진 범위의 리스트를 생성하고, 1은 소수가 아니므로 제외, 2부터 탐색을 시작한다.
2. 2의 배수들을 모두 제거하고, 다음 3의 숫자로 넘어간다.
3. 마찬가지로 3의 배수를 제거하고, 제거되지 않은 수로 넘어가 5의 숫자로 넘어가게 된다.
4. 2,3 번 과정을 리스트 끝까지 반복해서 남아있는 수를 모두 출력하면, 해당 수가 소수가 된다.