소수란?
소수는 1과 자기 자신만을 약수로 가지는 수를 의미한다.
예를 들어 7의 약수는 1과 7뿐이므로 7은 소수이다.
반면 8은 1, 2, 4, 8을 약수로 가지므로 소수가 아니다.
소수를 구하는 방법
1. 직접 나눗셈 (시간 복잡도: O(N))
2부터 N-1까지 모든 수로 나누어보아
어떤 수로도 나누어떨어지지 않으면 소수라고 판단할 수 있다.
하지만 수가 커질수록 연산량이 많아지는 비효율적인 방법이다.
#include <iostream>
using namespace std;
int main()
{
int n;
cin >>n;
if (n < 2)
return 0;
bool isPrime = true;
for (int i = 2; i < n; i++)
if (n % i == 0)
{
isPrime = false;
break;
}
cout << (isPrime ? "true" : "false") << '\n';
return 0;
}2. 제곱근까지만 나눗셈 (시간 복잡도: O(√N))
소수가 아닌 수는 두 수의 곱으로 표현되는 합성수다.
즉, N = a × b라고 하면, a와 b는 모두 1과 N 사이의 자연수이고
a와 b가 모두 √N보다 크면 a x b는 N보다 커지므로 성립할 수 없다.
따라서, 소수 판별 시 √N 이하의 자연수까지만 나눠보면 된다.
예를 들어 79를 살펴보자
79는 8 × 8 = 64와 9 × 9 = 81 사이의 숫자로, √79는 8과 9 사이에 있다.
a와 b는 자연수이므로 9보다 작은 8까지의 수만 나누어 보면 된다.
2부터 8까지 나누어 보았을 때, 79는 어떤 수로도 나누어떨어지지 않으므로 소수다.
#include <iostream>
using namespace std;
int main()
{
int n;
cin >> n;
if (n < 2)
return 0;
bool isPrime = true;
for (int i = 2; i *i <= n; i++)
if (n % i == 0)
{
isPrime = false;
break;
}
cout << (isPrime ? "true" : "false") << '\n';
return 0;
}3. 에라토스테네스의 체 (시간 복잡도: O(N log log N))
에라토스테네스는 고대 그리스의 수학자이자 천문학자로, 소수를 효율적으로 찾는 방법을 고안했다.
그가 만든 방법은 그의 이름을 따 ‘에라토스테네스의 체’ 라 불린다.
에라토스테네스의 체는 N 이하의 모든 소수를 한 번에 구하는 효율적인 알고리즘이다.
- 2부터 N까지의 수를 나열하고,
- 가장 작은 소수부터 시작해, 그 배수들을 모두 제거한다
- 제거되지 않고 남은 수는 모두 소수
50까지의 숫자 중 소수를 판별하려고 할 경우
7 < √50 < 8 이기 때문에 2부터 7까지 소수를 나누면 된다.
2의 배수인 4, 6, 8 ... 50까지 제거(파란색)
3의 배수 중 제거되지 않은 수인 9, 15, 21, 27, 33, 39, 45 제거(붉은색)
5의 배수 중 제거되지 않은 수인 25, 35 제거(노란색)
7의 배수 중 제거되지 않은 수인 49 제거(초록색)
남은 흰색이 모두 소수이다.
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
| 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
| 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 |
| 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 |
| 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 |
이때도 제곱근까지만 배수를 지우면 되기 때문에 매우 빠르다.
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n;
cin >> n;
if (n < 2)
return 0;
vector<bool> isPrime(n + 1, true);
isPrime[0] = isPrime[1] = false;
for (int i = 2; i * i <= n; i++)
if (isPrime[i])
for (int j = i * i; j <= n; j += i)
isPrime[j] = false;
for (int i = 2; i <= n; ++i)
if (isPrime[i])
cout << i << ' ';
cout << '\n';
return 0;
}