에라토스테네스의 체

에라토스테네스의 체는 고대 그리스 수학자인 에라토스테네스가 알아낸
소수를 구하는 방법이다.
에라토스테네스의 체는 배수를 제외한 모든 수는 소수라는 것으로 즉 1과 자기자신만으로 나누어지는 것은 소수라는 것이다.

에라토스네테서의 체는 먼저 1을 지우고 그후 2는 두고 2의 배수를 지운다
3도 마찬가지로 3을 두고 3의 배수는 지운다.
이걸 7까지 하면 돤다.

n까지의 소수를 구할때 루트n이하의 수의 배수를 지우면 된다.

사진출처:https://new.somai.co.kr/%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/