[C++] 소수 찾기 알고리즘

 

 

소수는 약수가 1과 자기 자신밖에 없는 수이다.

따라서 소수 판정은 2부터 n-1까지의 숫자로 나눠봄으로써 알 수 있다.

 

하지만 연산량을 조금 줄이기 위해서 한 가지 수학적인 사실을 이용할 수 있다.

- 소수는 2부터 $\sqrt{n}$까지의 정수로 나눠보면 알 수있다. 

 

간단하게 증명하자면, 만약 n이 1을 제외한 $\sqrt{n}$ 이하의 정수로 나누어 떨어지지 않는다고 가정하면, 

$\sqrt{n}$보다 큰 정수 a로 나누어 떨어진다. 하지만 a로 나누어떨어진다면 n/a로도 나누어 떨어진다는 뜻이고,

($a * \frac{n}{a} = n$ 이므로) 하지만 n/a는 $\sqrt{n}$보다 작은 정수이므로 가정에 모순이 발생한다.

따라서 1을 제외한 $\sqrt{n}$이하의 정수로 나누어떨어지지 않는다면 소수라고 판단할 수 있다.

 

이외에도 밀러 라빈 소수 판정방법, AKS 소수 판정법 등의 방법도 있지만, 여기에선 다루지 않는다.

---

위의 사실을 이용하여 아래와 같이 소수 판단 함수를 구현할 수 있다.

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

---

이번에는 위의 코드를 이용하여 1부터 100까지의 숫자를 확인해보자.

#include <iostream>
using namespace std;

bool isPrime(int n) {
	if (n < 2) return false;
	for (int i = 2; i * i <= n; i++) {
		if (n % i == 0) {
			cout << "소수아님";
			return false;
		}
	}
	cout << "소수";
	return true;
}

int main() {
	for (int i = 2; i <= 100; i++) {
		cout << i << ' ';
		isPrime(i);
		cout << endl;
	}
}

실행결과:

---

<에라토스테네스의 체를 이용한 소수 배열 구하기>

 

초등학교 또는 중학교에서 처음 소수에 대해서 배울때 1~100까지의 숫자를 쭉 써놓고, 2의 배수를 전부 지우고, 3의 배수를 전부 지우고.. 이런 식으로 해나가면서 1~100사이의 소수를 찾아본 적이 있을 것이다.

 

이러한 방법을 에라토스테네스의 체라고 한다.

---

#include <iostream>
#include <vector>
using namespace std;


vector<int> Eratosthenes(int n) {
	bool ary[100]; // 0부터 99까지 소수면 false.
	for (int i = 0; i < n; i++) ary[i] = false;
	ary[0] = ary[1] = true; // 0과 1은 소수가 아님

	vector<int> prime; 
	for (int i = 2; i < n; i++) {
		if (ary[i]) continue; // 소수가 아니면 continue
		prime.push_back(i); // 소수라면 리스트에 넣는다.
		// i보다 큰 i의 배수를 제외
		for (int j = i * 2; j < n; j += i) ary[j] = true;
	}
	return prime;
}

int main() {
	vector<int> prime = Eratosthenes(100);
	for (auto x : prime)
		cout << x << ' ';
}

 

실행결과: