[C++] 소수 구하기 (에라토스테네스의 체)

 

 

 

이 포스터에선 소수 구하기에 대해 알아보겠다.

Naive한 방식과 에라토스테네스의 체 방식을 코드로 살펴보도록하자.

 

먼저, 소수(Prime Number)란 무엇인가?

양의 양수가 1 혹은 자기 자신 밖에 없는 1보다 큰 자연수를 의미한다.

 

예를 들어,

8의 약수는 1, 2, 4, 8이기 때문에 소수가 아니다.

7의 약수는 1, 7이기 때문에 소수이다.

 

 

 

 

 

Naive 방식 코드

 

bool is_prime_number(int n)
{
	if (n < 2) 
		return false; // 예외 처리

	for (int i = 2; i * i <= n; i++)
		if (n % i == 0)
			return false;
	return true;
}

 

위 코드는 2 ~ Sqrt(N)에 대해 약수를 판별하여 소수를 구하는 알고리즘이다.

그렇다면 왜 N까지가 아닌, Sqrt(N)까지 구하면 되는걸까?

(Sqrt(N)은 루트 N을 의미)

 

약수가 존재한다는 것은 두 자연수의 곱이 발생한다는 의미이다. ( A * B = N )

여기서 중요한 점은 A * B = N이나 B * A = N이나 동일하다는 점이다.

따라서 우리는 동일한(서로 뒤집히는) 구간인 K * K = N까지만 체크하면 된다는 의미이다.

 

예를 들어, 16을 살펴보자

16은 (2, 4, 8, 16)의 약수를 가진다.

 Sqrt(16)인 4 이후를 체크할 필요가 있는가?

아니다, 이미 2 * 8을 체크했기 때문에 8은 체크할 필요가 없다.

따라서 N까지가 아닌,  Sqrt(N)까지만 체크하면 된다.

 

위 원리를 따르면 시간 복잡도는  O(log N)이다.

 

 

 

 

 

에라토스테네스의 체

하지만 만약 1 ~ N까지 각각에 대해 소수를 판별하는 프로그램은 위 코드가 어떨까?

시간 복잡도는 O(N * log N)이 되버린다.

그래서 우리는 미리 메모리를 할당하여 소수를 판별하는 에라토스테네스의 체를 볼 것이다.

 

 

 

원리는 다음과 같다.

 

 

1. 현재 포인트가 가리키는 숫자(K)의 배수를 메모리를 지운다.

 

 

 

 

2. K를 ++하여 1번을 동일하게 수행한다.

 

 

 

 

3. 이 과정을 K가 N이 될 때까지 수행한다.

 

 

 

이러면 1 ~ N에 대해 소수를 판별할 수 있다.

시간 복잡도를 따지면 이중 for문이기 때문에 O(N^2)이 되는 것처럼 보이지만,

뒤로 갈수록 for문을 생략하는 부분이 많아 일반적으로 O(N * log(log N))이다.

 

 

 

 

 

코드

// 메모리 할당
bool is_prime_numbers[10001];

int main()
{
	ios::sync_with_stdio(false); std::cin.tie(NULL); std::cout.tie(NULL);

	int answer = 0;
	int N;
	cin >> N;

	// 초기화
	for (int i = 2; i <= N; i++)
		is_prime_numbers[i] = true;

	// 에라토스테네스의 체 수행
	for (int i = 2; i <= N; i++)
		for (int j = i + i; j <= N; j += i)
			is_prime_numbers[j] = false;

	// 소수 체크
	for (int i = 2; i <= N; i++)
		if (is_prime_numbers[i])
			answer++;
	
	cout << answer << endl;

	return 0;
}