에라토스테네스의 체

1보다 큰 모든 정수는 소수와 합성수로 이루어진다.

 

소수는 1과 자기자신으로만 나누어떨어지는 수이고,

그 외 나머지를 합성수라고 한다.

 

1은 소수도 합성수도 아니다.

출처: https://sustainable-dev.tistory.com/32

 

소수를 찾는 방법은 에라토스테네스의 체 방식으로 찾을 수 있다.

 

1. 2를 제거하고, 2의 배수를 제거한다.

2. 3을 제거하고, 3의 배수를 제거한다.

3. 해당 방법을 sqrt(n)까지 반복한다. - sqrt는 루트

자신 * 자신 < n 때까지만 반복한다.