에라토스테네스의체

[알고리즘] 소수 알고리즘

소수를 구하는 알고리즘을 알아보자. 소수의 정의를 이용한 방법 N이 소수이면 2 ~ (N-1)로 나누어 떨어지지 않는다. 이 경우 2부터 N-1까지 연산이 필요하기 때문에 O(N)의 시간복잡도가 걸린다. 약수의 특징을 이용한 방법 N이 소수가 되려면, 2이상이고, N/2 이하의 자연수로 나누어 떨어지면 안된다. (N의 약수 중에서 가장 큰 것은 N/2보다 작거나 같다) 여전히 O(N)의 시간 복잡도를 갖는다. 약수의 특징을 이용한 방법2 모든 수의 약수는 루트 N을 기준으로 대칭을 이룬다. 루트 N의 값 왼쪽에 있는 값을 기준으로 값 들을 조합해 대칭 오른쪽에 있는 수의 값을 구할 수 있다. O(루트 N)의 시간 복잡도를 가진다. 컴퓨터에서 실수는 근사값을 나타내기 때문에, 루트 N과 같은 경우는 다음 ..