반응형
소수 판별 - 에라토스테네스의 체
에라토스테네스의 체 란?
- 소수 : 약수가 1과 자기 자신만 있는 1보다 큰 수.
- 에라토스테네스의 체 : 고대 수학자 에라토스테네스가 발견한 소수 판별 방법.
에라토스테네스의 체 예시
-
2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
-
2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
-
자기 자신을 제외한 2의 배수를 모두 지운다.
-
남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
-
자기 자신을 제외한 3의 배수를 모두 지운다.
-
남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
-
자기 자신을 제외한 5의 배수를 모두 지운다.
-
남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
-
자기 자신을 제외한 7의 배수를 모두 지운다.
-
위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.
에라토스테네스의 체 코드(C++)
#include <bits/stdc++.h>
#include <string>
using namespace std;
void prim(int n)
{
vector<bool> isNotPrime(n + 1,0);
if (n <= 1)
return;
for (int i = 2; i <= n; i++)
{
// isNotPrime[i] = true => 숫자 i 는 소수가 아니다.
if (isNotPrime[i])
continue;
for (int j = 2 * i; j <= n; j += i)
isNotPrime[j] = 1;
// 소수인 경우 처리할 문장
cout <<"소수 발견 : "<< i << endl;
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
prim(20);
return 0;
}
반응형
'알고리즘 > 알고리즘 이론' 카테고리의 다른 글
투 포인터, 슬라이딩 윈도우 기법 (1) | 2020.11.29 |
---|---|
문자열 탐색 자료구조 - 트라이(Trie) (0) | 2020.11.29 |
다이나믹 프로그래밍(Dynamic Programming, DP) (0) | 2020.11.24 |
최소 비용 신장 트리 - 프림(Prim) 알고리즘 (0) | 2020.11.23 |
최소 비용 신장 트리 - 크루스칼(Kruskal) 알고리즘. (0) | 2020.11.23 |
댓글