[C++] 소수 판별법, 소수 개수 구하는 법

소수: 2보다 크고 자기 자신 외에 약수를 가지지 않는 수

---

1. 자연수 N이 소수인지 판별하는 법

: 2보다 크거나 같고, 루트N보다 작거나 같은 자연수로 나누어 떨어지지 않는지 확인하기.

: 시간복잡도 루트N

 

* 왜 루트 N 까지?

자연수 N이 소수가 아니라면 N = a X b로 나타낼 수 있습니다.(a와 b는 자연수이고 N의 약수 조합)

 

이 때, a > b라면 두 수의 위치를 바꿔가며 항상 a <= b로 만들 수 있을 것입니다.

그리고 두 수 a와 b의 차이가 가장 작은 경우는 루트 N일 때(제곱근일 때) 이므로 루트N까지만 검사를 해보면 됩니다.

​

24를 예로 들어보겠습니다. 24는 소수가 아니므로 24의 약수는 1,2,3,4,6,8,12,24가 있을 겁니다. 이 때, 24를 두 수의 곱으로 표현해보면 1X24, 2X12, 3X8, 4X6으로 나타낼 수 있습니다.즉, 흔히 소수를 구할 때 N/2까지 계산해보는데 1,2,3으로 나누었을 때 이미 24, 12, 8 또한 소수가 아니라는 것을 알 수 있습니다.

 

따라서 두수의 차이가 가장 작은 경우인 루트N까지만 검사를 해보면 되는 것입니다.(루트24 = 4.xxxx 이므로 4까지만 검사하면 됩니다.)

 

* 코드

#include <iostream>
using namespace std;

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

int main() {
	int n;
	cin >> n;
	bool result = prime(n);

	cout << result << endl;

	return 0;
}

 

2. N까지의 수 중에 소수 개수 구하는 법

: 에라토스테네스의 체 방법을 사용합니다.

: 시간복잡도 O(N*log(logN))

 

* 에라토스테네스의 체란 ?

2부터 N까지 모든 수를 써놓고, 2부터 그 배수를 모두 지우면서 소수를 찾는 방법입니다. 이 때, 아직 지워지지 않은 수는 소수라고 할 수 있으므로, 소수를 찾을 수 있는 것입니다. 이 때도 역시 위에서 본 방법처럼 루트N까지만 반복실행하면 됩니다.

 

예를 들어, 1부터 100까지라면 11X11은 121로 100을 넘기 때문에 더이상 수행할 필요가 없습니다.

따라서 10까지만 에라토스테네스의 체를 구하면 되니까 시간복잡도가 훨씬 짧겠죠~

 

* 코드

#include <iostream>
using namespace std;

int main() {
	int prime[100]; //소수를 저장할 변수
	int pn = 0; //소수의 개수
	bool check[101] = { false, }; //지워졌으면 true
	int n = 100; //100까지의 소수

	for (int i = 2; i <= n; i++) {
		if (check[i] == false) {
			prime[pn++] = i;
			for (int j = i + i; j <= n; j += i) {
				check[j] = true;
			}
		}
	}
	for (int i = 0; i < pn; i++) {
		cout << prime[i] <<" ";
	}
	return 0;
}

---

관련 문제

https://www.acmicpc.net/problem/1929