소수 판별 알고리즘 . 1

하나의 수를 소수 판별할 때

 

 

 

위의 알고리즘은 약수의 성질을 이용하여 시간복잡도를 개선할 수 있다

 

 

 

하나의 소수가 아닌 다수의 소수를 판별해야 하면 에라토스테네스의 체 알고리즘을 활용하면 좋다

 

 

(중간 생략)

 

 

위에서 본 약수의 성질을 에라토스테네스의 체에서도 사용할 수 있다

N = 26 이라면 그 제곱근 값은 5와 6 사이일 것이다
그렇기에 5까지만 에라토스테네스의 체 알고리즘을 수행하면 더 효율적으로 답을 낼 수 있다

모든 약수는 가운데 약수(제곱근)을 기준으로 대칭이기 때문에
5까지만 확인하면 반대편 약수들은 다 사라졌기 때문에
5 이후부터의 수는 소수만 남게 된다

 

 

 

 

 

 

10억이라는 하나의 수가 소수인지 아닌지 판별하려고 에라토스테네스의 체를 이용한다면
소수 여부를 기록하기 위해 10억개의 자연수 데이터가 들어갈 수 있는 크기의 메모리 공간이
필요해서 메모리 측면에서 매우 비효울적이다