-
에라토스테네스의 체알고리즘 2024. 3. 4. 22:00
void eratos(int *arr, int n) { for (int i = 2; i * i < n; i++) { if (arr[i]) { for (int j = i * i; j <= n; j += i) { arr[j] = false; } } } }
*주의: 초기 배열은 완전히 true로 초기화되어 있어야 함
백준 문제 풀다가 시간 초과가 나와서 소수 알고리즘을 찾아봤습니다.
많은 수의 소수 여부를 판단할 경우에는 이 알고리즘이 좋을 것 같습니다.
알고리즘의 원리는, 어떤 소수 n의 배수는 소수가 아닐 것이기에
배수를 싹 지우는 과정을 반복하여 소수만 남기는 것입니다.
위 코드에서 n은 배열의 마지막 인덱스입니다. 즉 사이즈보다 1 작습니다.
시간복잡도는 O( n log logn )
'알고리즘' 카테고리의 다른 글
스택 응용, 백준 9935: 문자열 폭발 (0) 2024.03.05 이분탐색 3 - LIS (Longest Increasing Subsequence), 백준 12105 (0) 2024.03.02 이진탐색 2 - Parametric Search, 백준 1654 (0) 2024.03.02 이분 탐색(binary search) (0) 2024.02.25