[Algorithm] 에라토스테네스의 체

에라토스테네스의 접근

• 주어진 자연수 N이 소수이기 위한 필요충분 조건은 N이 N의 제곱근보다 크지 않은 어떤 소수로도 나눠지지 않는다.
• 소수가 되는 N이 자연수라면  sqrt(N)보다 작은 수로 나눠지지 않음

1, 2, 4, 5, 8, 10, 16, 20, 40, 80

• 자연수 N : 80,     sqrt(80) : 8.xxxx,    2부터 8.xxxx이하만 검색하면 이후의 값은 검사할 필요가 없음
• 1-80, 2-40, 4-20, 5-16, 8-10이기 때문에 8.xx이하만 검사하면 됨

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

	return true;
}

• 시간복잡도 : O(√ N)

 

에라토스테네스의 체

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

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

	return true;
}

int main()
{
	int num = 100;
	vector<bool> primeVec(num+1);
	fill(primeVec.begin(), primeVec.end(), true);

	for (int i = 2; i * i <= num; i++)
	{
		if (IsPrime(i))
		{
        	//i*i미만의 경우 가장 작은 약수는 i미만이므로 다른 수의 배수로 지워짐
			for (int j = i * i; j <= num; j += i)
			{
				primeVec[j] = false;
			}
		}
	}

	for (int i = 0; i < primeVec.size(); i++)
	{
		if (primeVec[i])
			cout << i << endl;
	}
}

• i의 배수를 지우기 위해서는 i*i 부터 확인하면 된다.
• i*i 미만의 수들의 경우, 가장 작은 약수는 i미만일 것이기 때문에 이미 다른 수의 배수로 지워짐