-
에라토스테네스의 체Programming/알고리즘 2020. 11. 15. 13:01
에라토스테네스의 체는 대표적인 소수(Prime Number) 판별 알고리즘이다.
에라토스테네스의 체 알고리즘은 한 두개의 소수를 판별하는 경우가 아닌 대량의 소수를 한꺼번에 판별할 때 사용한다.
에라토스테네스의 체는 우선 예를 들어 1부터 100까지의 수에서 소수를 판별한다고 하면 크기가 101인 int형 배열을 선언한다. 그리고 초기에 각 인덱스는 인덱스의 값으로 초기화를 시켜준다.
그 후 반복문을 통해 2의 배수, 3의 배수 ,4의 배수, ... 에 해당하는 인덱스의 값을 0으로 바꿔주는데 시간 복잡도를 줄이기 위해 이미 0인 부분은 continue를 사용하여 스킵되도록 한다.
#include <iostream> using namespace std; int number = 100; int a[101]; void isPrimeNumberSieve() { for (int i = 2; i <= number; i++) { a[i] = i; } for (int i = 2; i <= number; i++) { if (a[i] == 0) continue; for (int j = i + i; j <= number; j += i) { a[j] = 0; } } for (int i = 2; i <= number; i++) { if (a[i] != 0) printf("%d ", a[i]); } } int main() { isPrimeNumberSieve(); return 0; }
그러면 위와 같이 대량의 소수를 판별해내는 것을 확인할 수 있다!
'Programming > 알고리즘' 카테고리의 다른 글
플로이드 와샬 알고리즘 (0) 2020.11.16 다익스트라(Dijkstra) 알고리즘 (0) 2020.11.16 다이나믹 프로그래밍 (Dynamic Programming) (0) 2020.11.07 이진 트리와 순회 방식 (0) 2020.11.07 크루스칼 알고리즘 (Kruskal) (0) 2020.11.07