에라토스테네스의 체

📢 소수를 찾는 법

"고대 그리스 수학자 에라토스테네스가 발견한 소수(Prime number)를 구하는 방법"

1. 2(n)부터 소수를 구하고자 하는 구간의 자기 자신을 제외한 2(n)의 배수를 모두 지운다. 
	→ n : 2 ~ 구간의 끝
2. 남아있는 수(지워지지않은 수)가 바로 소수이다.

• 소수를 대량으로 가장 빠르게 구할 때 사용

• 시간복잡도 : O(Nlog(logN))

• 주어진 자연수 n이 소수이기 위한 필요충분 조건은 "n이 n의 제곱근보다 크지 않은 어떤 소수로도 나눠지지 않는다"
  (수가 수를 나누면 몫이 발생하게 되는데 몫과 나누는 수, 둘 중 하나는 반드시 N의 제곱근 이하이기 때문) → O((n-2)^1/2)
  

📃 코드

1. 나머지 연산 : O(n^2)
   

2. 에라토스테네스의 체
   

출력 X

출력 O

범위가 작을 때는 별 차이가 없지만 용량이 커지면 엄청난 시간차이가 있음을 알 수 있다.