에라토스테네스의 체

에라토스테네스의 체(Sieve Of Eratosthenes)

📔 에라토스테네스의 체(Sieve Of Eratosthenes) 란 대표적인 소수 판별 알고리즘 ( 소수: Prime Number ) 한꺼번에 많은 숫자의 소수를 판별할 때 사용 숫자 한개의 소수를 판별하는 기본 소수 판별 알고리즘의 시간복잡도는 O(N) 하지만 수학적으로 접근해서 시간복잡도를 O(N^(1/2)) 까지 줄일 수 있다. 에라토스테네스의 체를 사용하면 시간복잡도는 O(n log log n) 📔 에라토스테네스의 체(Sieve Of Eratosthenes) 구현 자연수 50까지의 숫자 중에서 소수를 구한다고 생각해보자. 기본 알고리즘을 사용할 경우 O(N*N^(1/2)) 의 시간복잡도가 생긴다. 에라토스테네스의 체를 이용하여 구해보자. 먼저 51개의 값이 1(True)인 리스트를 만든다. for..