소수의 성질

에라스토테네스의 체

임의의 자연수 n에 대해 그 이하의 소수를 찾는 가장 간단하고 빠른 방법이다. 예를 들어 1~100까지 숫자 중 소수를 찾는다 하자.

1. 일단 1~100까지 숫자 중 소수를 찾는다고 하자.
2. 1을 제거
3. 2를 제외한 2의 배수 제거
4. 3을 제외한 3의 배수 제거
5. 4를 제외한 4의 배수 제거 (이미 지워짐)
6. 5를 제외한 5의 배수 제거
7. \cdots
8. 99를 제외한 99의 배수 제거 (이미 지워짐)

이런 식으로 하면 된다.

• n을 2부터 n-1 사이의 수로 나눠준다
• 시간복잡도 = O(N)

응용 - 더 빠르게 구하기 (중요)

1~n 중 소수를 구한다고 치자.

1. 1을 제거
2. 2를 제외한 2의 배수 제거
3. 3을 제외한 3의 배수 제거
4. 4를 제외한 4의 배수 제거 (이미 지워짐)
5. 5를 제외한 5의 배수 제거
6. \cdots
7. \sqrt n 를 제외한 \sqrt n 의 배수 제거

• n을 2부터 해당 숫자의 \sqrt n 사이의 수로 나눠준다.
• 시간복잡도 = O(\sqrt N)으로 확 줄어든다.

문제는 \sqrt n 을 구현하는 방법.

파이썬의 경우에는 int(n**(0.5)) 으로 제곱근의 어림값을 설정한다.

베르트랑 공준

임의의 자연수 n에 대해, n ~ 2n 사이에 소수가 하나는 존재한다는 이론

역시 에라스토테네스 체를 응용한 방식으로 사용하면 풀리긴 한다.

골드바흐의 추측

1. 일단 1부터 10000까지 소수를 구한다.

2. 첫째값을 입력값의 절반부터 시작해 1씩 감소시킨다.

소수이면 둘째값이 소수인지 판별한다.

3. 만약 첫째값, 둘째값 모두 소수이면 결과를 출력한다.