알고리즘 개념
- 고대 그리스 수학자 에라토스테네스가 만들어 낸 방법으로, 마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 체'라고 부른다.
- 빠르고 정확하게 소수를 찾는 알고리즘
- n까지의 소수를 알고 싶을 때, n^1/2 이하의 수의 배수만 지우면 된다.
과정
- 배열 생성 후 초기화한다. (1은 소수가 아니니 지우고 시작)
- 2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 지운다.
- 2를 제외한 2의 배수를 지운다.
- 3을 제외한 3이 배수를 지운다.
- 반복
- 남아있는 수가 소수!
코드
vector<bool> arr(n+1);
arr[1] = true;
for(int i = 2; i <= sqrt(n); i++){
if(arr[i]) continue;
for(int j = i + i; j <= n; j += i)
arr[j] = true;
}
// 소수 출력
for(int i = 2; i <= n; i++)
if(!arr[i]) cout<< i << endl;
시간 복잡도
제곱근까지만 약수의 여부를 검증하면 O(N^1/2)로 가능하다.
728x90
'Algorithm > 개념정리' 카테고리의 다른 글
이분 탐색(Binary Seaerch) C++ / 장단점 / 시간복잡도 :: DANIDANI (0) | 2021.01.28 |
---|---|
힙정렬(Heap Sort) C++ / 장단점 / 시간복잡도 / 공간복잡도 :: DANIDANI (2) | 2021.01.21 |
병합정렬(Merge Sort) C++ / 장단점 / 시간복잡도 / 공간복잡도 :: DANIDANI (5) | 2021.01.19 |
퀵정렬(Quick Sort) C++ / 장단점 / 시간복잡도 / 공간복잡도 :: DANIDANI (1) | 2021.01.18 |
삽입정렬(Insertion Sort) C++ / 장단점 / 시간복잡도 / 공간복잡도 :: DANIDANI (0) | 2021.01.16 |