목록알고리즘 (9)
나의 잡다한 노트 및 메모
에라토스테네스의 체 (소수 판별 알고리즘)
에라토스테네스의 체의 쓰임새 - 소수를 대량으로 판별할 때 쓰인다. 시간 복잡도 - 어떤 숫자의 제곱근까지만 약수의 여부를 구하면 돼서 O(n^1/2)가 된다. 알고리즘 - 구해야 하는 소수의 범위로 배열을 할당 - 2부터 시작해서 배수인 숫자들을 지운다. 여기서 자기 자신은 지우지 않는다 - 이것을 전체 범위의 n^1/2까지 했다면 종료시킨다. 더 자세한 설명은 여기로! 그림으로 설명이 잘 돼있는 것 같다. https://namu.wiki/w/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98%20%EC%B2%B4
알고리즘
2022. 3. 9. 22:47