반응형 Miller-Rabin 썸네일형 리스트형 소수 판별법 - 에라토스테네스의 체, 밀러-라빈(Miller-Rabin) 소수판별법 어떠한 자연수 N이 소수인지를 판별하는 방법은 여러 가지 방법이 있다. 그중에서 너무 난도 높은 것은 제외하고 충분히 PS에서 쓸만한 방법을 알아보자. 우선, N이 소수인지를 판별하는 경우와 N이하의 소수가 몇개있는지, N이하의 소수를 모두 구하는 경우 두가지로 보통 나뉜다. 1. N을 2부터 N-1까지 모두 나누기 소수는 1또는 자기 자신으로만 나누어지기 때문에 위의 방법으로 N이 나누어 떨어지지 않는다면 N은 소수라고 할 수 있다. 만약, N이 어떤 두 수로 나누어진다고 한다면, N = p*q의 형태가 되고, p와 q 둘 중 하나는 반드시 $ \sqrt{N} $의 값 이하일 것이다. 따라서 N-1까지 나눌 필요는 없고, $ \sqrt{N} $까지만 나눠도 소수인지 판별이 가능하다. 물론, 이 방법을 .. 이전 1 다음
