[Algorithm] 소수 구하기

주: 이 포스트는 작성중입니다.

소수(Prime number)란 1과 자기 자신으로밖에 나누어지지 않는 1을 제외한 정수입니다.

 

다음은 C++로 구현한 가장 일반적인 소수구하기 알고리즘입니다.

#include <iostream>
using namespace std;
bool IsPrimeNumber(int n) {
	if (n <= 1) return false; //1 이하의 정수는 소수가 아님
	else if (n == 2) return true; //2는 짝수이면서 소수인 유일한 숫자이므로 예외처리
	else {
		if (n % 2 == 0) return false; //짝수는 모두 소수가 아님
		for (int i = 3; i*i <=n; i+=2) { //3부터 2씩 더해가며 소수 판정
			if (n % i == 0) return false; //1과 자기자신이 아닌 정수로 나누어 진다면 소수가 아님
		}
		return true;
	}
}

여기서 주목해야할 것은 반복문이 $i^2\leq n$까지 돈다는 사실입니다. 좀 더 직관적으로 말을 바꾸어보면 $i$는 $i\leq \sqrt{n}$까지 돈다는 것과 같습니다. 소수의 정의에 따르면 $1$과 자기자신이 아닌 정수로 나누어지면 소수가 아닙니다. 그럼 $3$부터 $n-1$까지 $2$씩 더해가면서 다 나누어주어야 할텐데 왜 하필 $\sqrt{n}$까지만 돌까요?

 

그 이유는 다음과 같습니다. 만약 어떤 수 $n$이 합성수라고 가정합시다. 그러면 $n=a*b (단, a, b\neq 1, n)$의 형태, 즉, a와 b를 약수로 가지는 형태로 나타낼 수 있습니다. 여기서 직관적인 이해를 통해 $a, b$가 최소 둘중 하나는 $\sqrt{n}$보다 작다고 할 수 있습니다. 그럼 1과 자기자신을 제외한 약수를 찾음으로써 $n$이 소수가 아니라는 반례를 찾는 for문은 $i\leq \sqrt{n}$까지만 돌면 된다는 것입니다.

 

여담으로, 위의 소스코드처럼 $i\leq \sqrt{n}$와 같은 형태가 아닌 $i*i\leq n$와 같은 형태로 for문의 조건식을 나타내면 #include<cmath>를 해주지 않아도 됩니다.