알고리즘
에라토스테네스의 체 (소수 판별 알고리즘)
peanutwalnut
2022. 3. 9. 22:47
에라토스테네스의 체의 쓰임새
- 소수를 대량으로 판별할 때 쓰인다.
시간 복잡도
- 어떤 숫자의 제곱근까지만 약수의 여부를 구하면 돼서 O(n^1/2)가 된다.
알고리즘
- 구해야 하는 소수의 범위로 배열을 할당
- 2부터 시작해서 배수인 숫자들을 지운다. 여기서 자기 자신은 지우지 않는다
- 이것을 전체 범위의 n^1/2까지 했다면 종료시킨다.
더 자세한 설명은 여기로!
그림으로 설명이 잘 돼있는 것 같다.