728x90
📗 에라토스테네스의 체 알고리즘
그리스의 수학자 에라토스테네스가 만들어 낸 소수를 구하는 방법으로
프로그래밍 알고리즘에서 소수를 구할 때도 적용하여 사용한다.
✔️ 에라토스테네스의 체 알고리즘의 원리
에라토스테네스의 체 알고리즘의 원리는
"소수의 배수인 수들을 전부 제외하면 소수만 남는다" 이다.
다시 말하면 소수의 배수들은 전부 소수가 아니기 때문에
소수의 배수들만 전부 제외하면 소수만을 구할 수 있는 것이다.
🚨CODE
// 에라토스테네스의 체
boolean[] prime = new boolean[n];
public static void SeiveOfEratosthenes(){
// true = 소수x , false = 소수
prime[0] = prime[1] = true;
for(int i = 2; i<=Math.sqrt(prime.length); i++){
// 소수가 아니면 넘어간다
if(prime[i])
continue;
// 소수이면
for(int j = i*i; j<prime.length; j+=i){
prime[j] = true;
}
}
}
✔️ 시간 복잡도
O(N * log(log N))
728x90
반응형
'알고리즘' 카테고리의 다른 글
다익스트라 알고리즘 - Dijkstra (0) | 2024.02.22 |
---|---|
이분 탐색 - Binary Search (0) | 2023.11.11 |
그래프 탐색 - DFS & BFS (0) | 2023.10.27 |
삽입 정렬 - Insertion Sort (0) | 2023.10.18 |
선택 정렬 - Selection Sort (0) | 2023.10.17 |