[C++] 소수 판별하기

안녕하세요. 오늘은 C++에서 소수를 판별하는 방법들을 알아볼게요.

 

소수는 1과 자기 자신만을 약수로 가지는 수입니다. 대신 1은 소수가 아니에요.

 

소수 판별은 가끔 코테에서 나올 때 자신이 없어지는 유형 중 하나인데요.

C++에서는 정형적인 해결 방법이 있으니 기억해두면 유용할 것 같습니다.

 

---

방법 1. 직관적으로 구하기 ( O(N) )

쉽게 떠올릴 수 있는 방법이에요. 

 

일일이 나눠주면서 약수가 있는지 검사하는 방법입니다.

 

바로 코드를 볼게요.

bool isPrime(int n) {
	if (n == 1)
		return false;

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

	return true;
}

 

---

방법 2. 제곱근 이용하기 ( O(√N) )

위와 같은 과정을 거치면서 실행시간을 더 줄이는 방법이 있습니다. 제곱근을 이용하는 건데요.

 

어떤 수의 제곱근보다 작은 자연수들만 고려하면 그 수가 소수인지 판별할 수 있습니다.

 

제곱근보다 큰 수는 왜 고려를 하지 않아도 되는지는 설명이 필요한 일입니다.

수학을 좋아하는 편은 아니라서 여기서는 넘어갈게요.

제곱근이 정수라면 그 수는 당연히 소수가 아니게 된다던지 나름 재미있는 트릭입니다.

 

직접 해보니 정수 범위 내에서는 빠르게 돌아가는 거 같아요. 코드도 간단하고 자주 사용할 거 같은 방법입니다.

 

아래는 n이 소수인지 판별하는 C++ 코드

bool isPrime(int n) {
	if (n == 1)
		return false;

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

	return true;
}

 

---

방법 3. 에라토스테네스의 체 ( O(Nlog(logN)) ) 

에라토스테네스의 체는 위 두 방법보다 빠른 방법이 필요할 때 사용하는 알고리즘입니다.

 

알고리즘 이름의 '체'가 무슨 말인지 궁금해서 찾아보니 가루 같은 걸 거를 때 사용하는 체를 말하는 거 였어요. 약수가 아닌 수를 체처럼 거른다고 해서 붙은 이름이라고 하네요.

 

에라토스테네스의 체는 예시와 함께 보면 이해가 잘되는 알고리즘입니다. 아래 그림은 소수가 아닌 수를 빨간색으로 표시하는 표에요.

 

위 그림에서 2는 소수이지만 2의 배수는 소수가 아니겠죠. 표시를 해보겠습니다.

 

마찬가지로 3도 소수이지만 3의 배수는 소수가 아니에요.

 

다음은 4인데요. 표를 보시면 4는 2를 고려할 때 이미 처리가 되었습니다. 즉 4의 배수도 이미 모두 처리가 된 상태라는 거죠.

 

마지막으로 5의 배수까지 표시하고 나면 표에는 더 이상 소수가 아닌 수가 남지 않습니다. 1부터 30까지의 소수를 모두 구한 건데요. 체라는 표현이 이해가 되는 거 같으면서도 잘 모르겠네요.

 

에라토스테네스의 체를 사용해서 1부터 N까지의 소수를 판별하는 C++ 코드는 다음과 같습니다.

int erato[1005];
void eratothenes(int N) {
	for (int i = 2; i <= N; i++)
		erato[i] = 1;

	for (int i = 2; i <= N; i++) {
		if (erato[i] == 1) {
			for (int j = i * 2; j <= N; j += i)
				erato[j] = 0;
		}
	}
}

eratothenes 함수를 호출하면 erato 배열의 소수인 인덱스는 모두 1로, 소수가 아닌 수는 0으로 표시됩니다.

 

도움이 되셨다면 하트와 댓글 부탁드립니다.