목록Eratosthenes (1)

갱주

에라토스테네스의 체

에라토스테네스의 체?에라토스테네스의 체(Sieve of Eratosthenes)는 주어진 범위 내에서 모든 소수를 찾는 알고리즘입니다.이 알고리즘은 소수의 배수를 제거하는 방식으로 동작하며, 시간 복잡도는 O(n log log n)입니다.(소수란 1과 자기 자신만을 약수로 가지는 수)알고리즘 설명2부터 n까지의 자연수를 나열합니다.가장 작은 수인 2를 소수로 선택합니다.2를 제외한 2의 배수들을 모두 지웁니다.다음 남은 수 중 가장 작은 수를 소수로 선택하고, 그 수의 배수들을 모두 지웁니다.이 과정을 반복하여 선택된 소수의 배수를 모두 제거합니다.더 이상 지울 배수가 없으면 남아 있는 수들이 모두 소수입니다. 구현 코드def eratosthenes_sieve(n): # 0과 1은 소수가 아니므로 ..
알고리즘 2024. 10. 15. 10:58
이전 Prev 1 Next 다음