소수란?

• 소수(Prime Number)란 1과 자기 자신으로만 나누어지는 수를 의미 → 약수가 2개

• 합성수(Composite Number)란 약수의 개수가 3개 이상인 수

• 단, 1은 소수도 아니고 합성수도 아님

소수 판별법(Primality Test)

$N$의 약수의 개수를 세는 방법

1. 1부터 $N$까지의 수로 $N$을 나눔

• $O(N)$의 시간 복잡도

2. 1부터 $\sqrt N$까지의 수로 $N$을 나눔

• $O(\sqrt N)$의 시간 복잡도

3. 만약 1부터 $N$까지의 수들 중 모든 소수를 판별하게 된다면, 기존의 시간 복잡도 X $N$이기 때문에 개선 필요

에라토스테네스의 체(Sieve of Eratosthenes)

동작 순서

1. 2부터 $N$까지 모든 정수를 적는다.

2. 아직 지우지 않은 소수 중 가장 작은 소수를 찾는다. 이 수를 $P$라고 한다.

3. 아직 지우지 않은 수들 중, $P$의 배수를 크기 순서대로 지운다.

4. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.

• $O(N log(logN)$의 시간 복잡도

for (int i = 2; i <= N; ++i) {
	// 아직 지우지 않은 수 중 가장 작은 소수를 찾음
	if (is_prime[i]) {
    	for (int j = i * 2; j <= N; j += i) {
        	// j가 소수가 아님을 is_prime 배열에 체크
        	if (is_prime[j]) {
            	is_prime[j] = false;
            }
		}
	}
}

for i in range(2, N+1):
	# 아직 지우지 않은 수 중 가장 작은 소수를 찾음
	if is_prime[i]:
    	for j in range(i*2, N+1, i):
        	# j가 소수가 아님을 is_prime 배열에 체크
        	if is_prime[j]:
            	is_prime[j] = False

bool 자료형 배열인 is_prime 안의 모든 요소들에 대하여, 처음에 True로 초기화
1은 소수가 아니므로, i값은 2부터 시작
j는 i만큼 계속 커지도록 하여, i를 제외한 N이하의 모든 i의 배수를 빠르게 체크
이후, is_prime[i] = True인 모든 i의 값은 소수가 됨