알고리즘/소수 구하기 - 에라토스테네스의 체

에라토스테네스의 체 알고리즘 - 소수 구하기 알고리즘

우리는 에라토스테네스의 체(Sieve of Eratosthenes)라는 방법을 통해 보다 쉽게 소수를 찾아낼 수 있습니다. 이름 그대로 체를 통해 무언가를 걸러내듯이 소수를 찾는 방법입니다. 일반적으로 소수만 구하려면 2중 for문을 이용해 시간 복잡도는 O(N^2)라고 판단할 수 있다. 에라토스테네스의 체 알고리즘을 이용하면 시간 복잡도는 O(Nlog(logN))이다. 배수를 삭제하는 연산으로 바깥 for문을 생략하는 경우가 발생하기 때문이다. 찾을 범위까지 수를 나열한 다음, 소수가 아닌 1을 지웁니다. 1 다음으로 큰 소수인 2를 남겨두고 2의 배수를 모두 지웁니다. 2 다음으로 큰 소수인 3을 남겨두고 3의 배수를 모두 지웁니다. prime(n) 다음으로 큰 소수인 prime(n+1)을 남겨두고 ..