소수 찾는 알고리즘 : 에라토스테네스의 체

오늘 날씨는 야옹·2024년 2월 4일

백준

알고리즘

목록 보기

4/4

소수를 찾는 데 for나 while문을 돌릴 수도 있다.
그치만 귀찮기도 하고... 만약 여러 개의 소수를 찾아야 하는 경우, 시간복잡도는 O(n^2)이 든다.

에라토스테네스의 체는, 여러 숫자에 대해 소수인지 아닌지를 판별해야 할 때 유용하다.
시간복잡도도 O(n log (log n) )이라고 한다.

에라토스테네스의 체 방법

1) 2부터 소수를 구하고자 하는 구간의 모든 수를 나열함.
2) 2는 소수이므로 오른쪽에 2를 쓰고, 자기 자신을 제외한 2의 배수를 모두 지움.
3) 남아 있는 수 중 가장 작은 소수 즉, 3을 오른쪽에 쓰고, 3을 제외한 3의 배수를 모두 지움.
이를 계속하여 반복하는데, 11^2 > 120이므로 11보다 작은 수의 배수들만 지우면 됨

어떤 수 n에 대하여, 이 수가 소수인지 아닌지를 판별하려면, n/2까지의 수가 나누어지는지 일일이 확인할 필요가 없다. n의 제곱근까지만 확인하면 된다.

장점

시간복잡도가 줄어듦. O(n log (log n) )

단점

그러나 공간복잡도, 즉 메모리는 많이 필요하게 됨.

관련 문제 풀이

백준1929

#include <iostream>
using namespace std;

const int MAX = 1000000 + 1;
int num[MAX];

int main()
{
	int minNum, maxNum;
	cin >> minNum >> maxNum;

	// 초기화
	num[0] = -1;
	num[1] = -1;
	for (int i = 2; i <= maxNum; i++)
	{
		num[i] = i;
	}
	
	for (int index = 2; index * index <= maxNum; index++)
	{
		if (num[index] == index) // 소수라면 걸러냄
		{
			for (int i = index * index; i <= maxNum; i += index)
			{
				num[i] = -1;
			}
		}
	}
	
	for (int i = minNum; i <= maxNum; i++)
	{
		if (num[i] == i) cout << i << '\n';
	}
}

2시간이나 붙잡았는데
시간 초과인 이유가 너무 어이없다
'\n' 대신 std::endl 썼다고...... 눈물

참고

오늘 날씨는 야옹

이전 포스트

소수 찾는 알고리즘 : 에라토스테네스의 체

알고리즘

에라토스테네스의 체 방법

장점

단점

관련 문제 풀이

최대공약수(GCD), 최소공배수(LCM) 알고리즘

0개의 댓글