소수 찾기

Goal

• 소수 찾기 알고리즘에 대해 설명할 수 있다.
• 상황에 맞게 소수 판별 알고리즘을 사용할 수 있다.

---

소수찾기 방법

1. 2~n-1 까지 수와 나눠보고 소수 판별
2. n/2 범위까지 홀수 값으로 소수 판별
3. 제곱수까지 확인해보고 소수 판별
4. 에라토스테네스의 체

 

1. 2 ~ n-1 까지 수와 나눠보고 소수 판별

구현 코드

bool isPrime(int n)
{
	if (n < 2) return false;

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

	return true;
}

 

시간 복잡도 : O(n)

 

3. n/2 범위까지 홀수 값으로 소수 판별

구현 코드

bool isPrime(int n)
{
	if (n < 2) return false; // 1이하
	
	if (n == 2) return true; // 2인경우
	
	if ((n & 1) == 0) return false; // 짝수인 경우


	for (int i = 3, max = n >> 1; i < max; i += 2) // n/2 까지, 3이상의 홀수
	{
		if (n % i == 0)
		{
			return false;
		}
	}

	return true;
}

 

시간 복잡도 : O(n/4) = O(n)

 

3. 제곱수까지 확인 해보고 소수 판별

자연수 n이 소수가 아니라면 다음 식이 성립한다.

n = a * b (2<=a<n, 2<= b < n , a, b는자연수)

min(a,b) <= $\sqrt{n}$ 이므로, 제곱근 까지만 확인해도 소수 판별이 가능하다.

 

참고) 제곱수까지만 확인해도 되는 이유

(1) n의 양의 제곱근을 m이라 할 때, 다음 식이 성립한다.

m = sqrt(n)  <=>  m * m = n

 

(2) 만약 n이 소수가 아니라면 두 자연수의 곱으로 표현 될 수 있다. (단, 1 < n)

n = a * b

 

그리고 (1), (2) 식을 통해 다음이 성립함을 알 수 있다. (n이 소수가 아니라는 가정 하에)

a * b = m * m

 

또한, 1 < n 이므로 n의 최소값은 4이고 다음 식이 성립한다.

2 <= a < n, 2 <= b < n

 

m은 실수이고, a, b는 자연수이므로 다음과 같은 3가지 케이스가 존재할 수 있다.

1. a > m <=> b < m
2. a < m <=> b > m
3. a = m <=> b = m

위 식에서 다음 식이 성립함을 알 수 있다.

min(a,b) <= m

=> m까지만 확인해보면 소수인지 아닌지 확인할 수 있게 된다.

 

설명)

n = 100일 때,

점차적으로 증가하는 a값은 다음과 같이 나타낼 수 있다.

2, 4. 5, 10, 20, 25 , 50

이때, b의 값은

50, 25, 20, 10, 5, 4, 2

 

n의 제곱근을 기준으로 이전에 나왔던 숫자들이 서로 반전이 되므로, n의 제곱근 전까지의 처음 나오는 숫자들로 소수를 판별하면된다.

구현 코드

bool isPrime(int n)
{
	if (n < 2) return false; // 1이하
	
	if (n == 2) return true; // 2인경우
	
	if ((n & 1) == 0) return false; // 짝수인 경우

	for (int i = 3; i * i <= n; i += 2) // n/2 까지, 3이상의 홀수
	{
		if (n % i == 0)
		{
			return false;
		}
	}

	return true;
}

 

시간 복잡도 : O($\sqrt{n}$)

 

4. 에라토스테네스의 체

N이하의 소수를 모두 구할 때 사용하는 알고리즘으로

1개의 소수가 아닌 여러개의 소수를 한꺼번에 구할 때 사용되는 알고리즘이다.

 

다음 그림은 2이상 120이하의 수 중에서 소수를 찾는 과정을 나타낸다. 

 

알고리즘 설명

1. 2부터 n까지 소수를 구하고자 하는 구간의 모든 수를 나열한다. 
2. 2 ~ n 까지 다음 과정을 반복한다. (증가하는 수를 i라고 가정)
   1. i가 소수라면 i보다 큰 배수는 소수가 아니므로 소수가 아니라고 체크한다.
   2. i = i+1

그림의 경우, $11^{2} > 120 $이므로 11보다 작은 수의 배수들만 지워도 충분하다.

즉, 120보다 작거나 같은 수 가운데 2, 3, 5, 7의 배수를 지우고 남는 수는 모두 소수이다.

위키백과 참고

 

위 알고리즘은 좀 더 최적화가 가능한다.

i보다 큰 배수를 소수가 아니라고 체크할 때, i * i 이전의 값들은 이미 확인이 된 값이기 때문에 체크할 필요가 없다.

 

구현 코드

void eratos(int n)
{
	if (n <= 1) return;

	/*
	2부터 n까지 n-1개를 저장할 수 있는 배열 할당
	배열 참조 번호와 소수와 일치하도록 배열의 크기는
	n+1 길이만큼 할당(인덱스 번호 0과 1은 사용하지 않음)
	*/
	bool* primeArray = new bool[n + 1];

	for (int i = 2; i <= n; i++)
		primeArray[i] = true; // 처음엔 모두 소수라고 가정

	/*	
	만일, primeArray[i]가 true이면
	i이후 배수는 i를 약수로 가지므로, 배수에 false값을 준다.
	
	primeArray[i]가 false이면 소수가 아니므로 검사할 필요가 없다.

	또한, i*k (k < i) 까지는 이미 검사되었으므로
	j시작 값은 i*2 에서 i*i로 개선할 수 있다.
	*/
	for (int i = 2; i * i <= n; i++)
	{
		if (primeArray[i])
		{
			for (int j = i * i; j <= n; j += i)
			{
				primeArray[j] = false;
			}
		}
	}
}

 

시간 복잡도 : O(n log log n)

 

시간 복잡도 설명

최적화를 하지 않은 경우 어뜬 보면, 이중 for문이라 O($n^2$)일 것 같지만, 그렇지 않다. 
표에 빗금을 치는 횟수를 대략적으로 따져보면 N/2 + N/3 + N/4 + N/5 + ... + N/(N-1) + N/N 정도가 되는데,

1 + 1/2 + 1/3 + ... 꼴의 합이므로 O(logN)이 된다.

 

   (1) + (1/2 + 1/3) + (1/4 + 1/5 + 1/6 + 1/7) + ...
≤ (1) + (1/2 + 1/2) + (1/4 + 1/4 + 1/4 + 1/4) + ...
≤ 1*(1) + 2*(1/2) + 4(1/4) + ...

 

이런 식으로 상한을 취하면 "1" 값을 가지는 항이 O(logN)개 생기게 되어서 O(logN)의 상한임을 보일 수 있으므로, 

알고리즘이 빗금을 치는 횟수는 O(NlogN)이다. 이 테크닉은 가끔씩 쓸데가 있으니 기억해 두자.

참고) 라이님 블로그

이떄, i+i를 i*i로 개선했을 때의 알고리즘은 O(n log log n)이 된다.

이는 수학적 배경이 깊이 깔려 있으므로.. 참고 정도만 하고 넘어가자

에라토스 테네스의 체 시간 복잡도 설명

 

References

http://blog.naver.com/PostView.nhn?blogId=kks227&logNo=220793360258

위키백과 에라토스테네스의 체