C++ 소수 찾기 알고리즘 2가지

N이라는 수가 소수인지 판단하는 방법은 가장 쉬운 방법으로는 2부터 n-1까지 나눈다음 나누어 떨어지는게 하나도 없는지 확인하면 된다. 하지만 이 방식은 시간복잡도가 O(n)이 나오므로, 상당히 비효율적이다.

 

1. √n 까지만 판정하는 방법

이 때 중요한 것은 , 2부터 n-1까지 나눌필요가 없고 2부터 √n 까지만 계산하면 된다는 것이다. 따라서 시간복잡도는

O( √n )이 나오게 된다. 왜 √n 까지만 계산하면 되는 것일까? 숫자 18을 예시로 살펴보자.

18은

1*18

2* 9

3*6

6*3

9*2

18*1 

로 나타낼 수 있다. 여기서 살펴보면 위3개와 아래 3개는 각각 대칭을 이룬다. 왜냐하면 어떤 수 x에 대하여 소인수 분해할 때 반드시 X= Y*Z로 Y와 Z는 반드시 짝을 이뤄야하기 때문이다. 즉, Y가 정해지면 Z는 반드시 정해진다. 18의 소인수 분해에서보면 위의 3개는 좌측 변수가 오른쪽 변수보다 작은 모든 짝들을 적어놓은 것이다. 이후는 좌측 변수가 우측 변수보다 큰 짝들을 적어놓은 것이다. 따라서 반드시 위 3개, 아래 3개가 대칭이 될 수 밖에 없다. 

1*18 과 18*1

2*9와 9*2

3*6과 6*3

이렇게 일대일 대응로 완전히 대칭이 된다.

대칭의 기준은 √n이 된다.  X=Y*Z에서 Y가 Z보다 작은경우만 따져도 일대일 대응이기 때문에, Y가 Z보다 큰 경우를 이미 따져진 것이나 마찬가지가 된다. 따라서 2부터 √n 까지만 판정하면 소수인지 아닌지 판가름 할 수 있게된다.

 

 

2. 에라토스테네스의 체

에라토스테네스의 체는 어떤 하나의 수가 소수인지 판단하는데 쓰이는 방법보다는,  N이하의 모든 소수를 판정하는데 유용한 기법이다. 시간 복잡도는 O(n*log(log n))이 된다.

 

출처: 위키백과 (에라토스테네스의 체)

 

 

이 방법은 2이상 n이하의 수 i에 관해서, i를 제외한 i의 배수를 모두 지워가면서 소수가 아닌 것들을 걸러내는 방식이다.

왜 이러한 방식으로 제거해나가면 소수만 남게 될까?

 

120을 예를들어보자

 

2를 남기고 2의 배수를 모두 제거한다. 

3을 남기고 3의 배수를 모두 제거한다

4의 배수는 이미 2에의해 제거됐으므로 넘어간다

5를 남기고 5의 배수를 모두 제거한다.

6의 배수는 이미 2에의해 제거됐으므로 넘어간다

7을 남기고 7의 배수를 모두 제거한다.

...

 

여기서 제거한다는 거는 알겠는데, 왜 소수만 남게 된다는 것일까?

다음 문장에 집중해야한다. "x를 남기고 x의 배수를 모두 제거한다"  여기서 x를 남긴다는 것은 x를 소수로 판정한다는 것이다. 왜냐하면 x이전의 1을 제외한 임의의수 y에 관해서, "y를 남기고 y의 배수를 모두 제거한다"를 했음에도 불구하고 살아남았다는 것은 1과 x자기자신을 제외한 배수가 없다는 뜻이기 때문이다.

 

이것을 c++ 코딩으로 표현하면 다음과 같다.

 

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int n;
	cin >> n;

	vector<int> v(n+1, 1); //1은 살아있음, 0은 제거된상태

	for (int i = 2; i <= n;i++)
	{
		if (v[i] == 0) continue;
		
		for (int j = i * 2; j <= n; j += i)
		{
			if (v[j] == 1) v[j] = 0;		
		}
	}


	for (int i = 2; i <= n; i++)
	{
		if (v[i] == 1) {
			cout << i << endl;
		}
	}
}

 

 

여기서 시간 복잡도를 더 줄일 수 있는 방법이 있다.

 

다음과 같이 코딩하면 된다.

#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

int main()
{
	int n;
	cin >> n;

	vector<int> v(n+1, 1); //1은 살아있음, 0은 제거된상태

	for (int i = 2; i <= sqrt(n);i++)
	{
		if (v[i] == 0) continue;
		
		for (int j = i * i; j <= n; j += i)
		{
			if (v[j] == 1) v[j] = 0;		
		}
	}


	for (int i = 2; i <= n; i++)
	{
		if (v[i] == 1) {
			cout << i << endl;
		}
	}
}

 

i를 n까지 안 따지고 √n 까지 따졌다. 왜냐하면 또 예시를 n을 120으로 들어보자. i가 11일때로 따져보자. 그러면 n이하의 11의 배수를 지워나가는 작업을 해야하는데 11의배수는 가장 커봤자 11*10이다. 11*12가 될 수가 없다. 즉 좌측 변수가 우측변수보다 큰 상태가 된다. 좌측변수가 우측변수보다 크다는 뜻은? 우측 변수는 이미 i가 11이기 이전에 i에서 이미 다 판정 했다는 뜻이된다. 즉 11*10이든 11*5든 이것은 i가 5일때와 10일때 이미 다 판정해버린상태이다. 따라서 √n까지만 판정하면 된다.

 

그리고 j는 왜 i*i부터 판정을 할까? 이것또한 좌측변수와 우측변수로 풀어낼 수 있다. 예를들어 j=i*i가아니라 j=i*(i미만의 수)부터 판정을 한다고 치자. 그건 현재 i가아닌 이전의 i에서 이미 판정을 해버린 상태이기 때문에 더이상 판정을 할 필요가 없다는 뜻이된다. 다시 예를들어 i가 5인상태를 살펴보자. j=5*5부터 하면되는데, 5*2나 5*3을 판정할 필요가 있을까?

5*2는 이미 i가 2일때 판정이됐고, 5*3은 i가 3일때 판정이 됐다. 굳이 반복해서 판정할 필요가 없다는 것이다. 따라서 i*i부터 판정하면 된다. 

 

이해하기 복잡할 수 있지만, 차근차근 숫자를 대입해가면서 이해해보자!

 

정리하자면 하나의 소수를 판정할 때, 특히나 그 수가 매우 크다면 2부터 √n 까지 나눠보는 방식으로 소수를 판정하면 되겠고, n이하의 모든 소수를 판정해야하는 범위 문제가 나온다면 에라토스테네스의 체를 이용하는 방식을 이용하면 되겠다.