완전 탐색

소수의 정의를 그대로 이용하여 완전 탐색을 통해 찾을 수 있다.

O(N) 의 시간복잡도를 갖는다.

• 2 부터 100 까지의 소수 구하기

#include <iostream>

bool isPrime(int Num)
{
	if (1 == Num)
		return false;

	for (int i = 2; i < Num; ++i)
	{
		if (0 == Num % i)
			return false;
	}

	return true;
}

int main()
{
	int N = 0;
	std::cin >> N;

	if (isPrime(N))
		std::cout << N << "은 소수입니다.";
	else
		std::cout << N << "은 소수가 아닙니다.";

	return 0;
}

100
100은 소수가 아닙니다.

23
23은 소수입니다.

시간 복잡도 줄이기

<aside>

합성수 N에서 1을 제외한 가장 작은 약수는 $\sqrt{N}$ 이하이다.

</aside>

위의 증명을 이용하면 시간 복잡도를 O(N^(1/2)) 로 줄일 수 있다.

#include <iostream>

bool isPrime(int Num)
{
	if (1 == Num)
		return false;

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

	return true;
}

int main()
{
	int N = 0;
	std::cin >> N;

	if (isPrime(N))
		std::cout << N << "은 소수입니다.";
	else
		std::cout << N << "은 소수가 아닙니다.";

	return 0;
}

20
20은 소수가 아닙니다.

59
59은 소수입니다.

에라토스테네스의 체

에라토스테네스의 체는 소수를 찾는 방법 중 하나이다.

대량의 소수들을 구해야할 때 유용한 알고리즘으로 O(N^(1/2)) 의 시간복잡도를 갖는다.

소수란 1 과 자기 자신만을 약수로 가지는 수이며, 1 을 제외한 수의 배수가 되는 수는 소수가 아니다. 에라토스테네스의 체는 이러한 소수의 개념을 이용한 알고리즘이다.

임의의 수 N 까지의 소수를 구하고자 할 때 2 부터 N 의 제곱근까지 돌며 모든 배수들을 소수에서 제외시킨다.

• 2부터 100까지의 소수 구하기

#include <iostream>
#include <vector>

int main()
{
	int N = 100;
	std::vector<bool> Num(N + 1, true);
	for (int i = 2; i < sqrt(N); ++i)
	{
		if (Num[i])
		{
			// i * k (k < i) 까지의 수는 이미 검사했으므로 i * i 부터 검사
			for (int j = i * i; j <= N; j += i)
				Num[j] = false;
		}
	}

	std::cout << "2 ~ " << N << " 사이의 소수는" << std::endl;
	for (int i = 2; i < Num.size(); ++i)
	{
		if (Num[i])
			std::cout << i << " ";
	}

	return 0;
}

2 ~ 100 사이의 소수는
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97