알고리즘

에라토스테네스의 체

소수를 찾는 방법으로 하나 외우고 있으면 좋을것 같다 소수를 찾는 코테 문제하나를 풀어봤는데 기존에 모든 경우의 수(2와 3부터 시작하는 모든 홀수) 를 넣어서 찾는 방법은 시간초과가 되어버렸다.(소수탐색 자체만 해도 O(n)이고 만약 두 소수의 곱으로 이뤄진 숫자에서 두 소수를 찾아라 하는 문제일 경우 반복문을 이용해야 되므로 O(n^2)의 경우가 되는 문제가 있었다.) 에라토스테네스의 체를 사용한다면 O(N^1/2)의 시간복잡도로 계산할수 있다 주로 대량의 소수를 한꺼번에 판별해야할 경우에 사용한다 방식(파이썬) 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다 2부터 시작해서 나열된 수에서 지워지지 않은 수 중 가장 작은 2를 소수로 선택하고 2의 배수를 지운다. 3도 지워지지 않았기 때문에 ..