반응형
소수는 1보다 크고 1과 자기 자신으로만 나눠지는 자연수입니다.
자연수 N이 소수임을 판별하는 방법은 2부터 n-1까지의 자연수로 자연수 N을 나눴을 때 나누어 떨어지는지 보면 됩니다.
만약 2부터 n-1까지의 자연수 중에 하나라도 나누어 떨어지면 자연수 N은 소수가 아닙니다.
그런데 이렇데 n-1까지 나누어 보는 방식은 O(N)의 시간 복잡도가 걸립니다.
n-1까지 나누어 떨어지는지 다 확인할 필요가 없고 sqrt(N)까지만 나누어 봐도 소수임을 판별할 수 있고 이때 시간 복잡도는 O(sqrt(N))입니다.
<C++ 소스 코드>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
#include <iostream>
using namespace std;
bool isPrime(int n) {
if (n <= 1) return false;
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) return false;
}
return true;
}
int main(void) {
cout << "input N : ";
int n;
cin >> n;
if (isPrime(n)) {
cout << n << " is prime number";
}
else {
cout << n << " is composite number";
}
return 0;
}
|
cs |
<증명>
자연수에서 두 개 이상의 소수의 곱으로 이루어져 있는 수, 1과 소수를 제외한 수를 합성수라고 합니다.
어떤 수가 합성수가 아님을 판별하면 그 수는 소수입니다.
자연수 N을 N = P X Q (P <= Q, P 와 Q 는 1과 N이 아닌 자연수)을 만족하는 합성수라고 가정했을 때
N = P X Q >= Q x Q = Q ^ 2
-> Q <= sqrt(N)
따라서 N은 sqrt(N)보다 작은 적어도 하나의 인수를 가지므로 sqrt(N)까지만 나누어보면 됩니다.
반응형
'알고리즘' 카테고리의 다른 글
[알고리즘] lower_bound, upper_bound (0) | 2023.07.21 |
---|---|
[알고리즘] 단절선(bridge or cut edge) (0) | 2021.12.19 |
[알고리즘] 단절점(Articulation Points or Cut Vertices) (0) | 2021.12.19 |
[알고리즘] 투 포인터 알고리즘(Two Pointers Algorithm) (0) | 2020.03.05 |
[알고리즘] 에라토스테네스의 체 알고리즘 (0) | 2020.03.04 |