ps:소수_판별
소수 판별 (Primality Test)
특정 수가 소수인지 판별
- 여러가지 방법이 있긴 하지만, 작은수에는 Trial division, 큰 수에는 밀러-라빈 알고리즘을 사용하면 된다
- 페르마 소수판별법 등은 몰라도 된다
Trial division
- 2부터 sqrt(n)까지의 모든 수에 대해서 n을 나누어 떨어지는 수가 있는지 확인해본다.
- 시간복잡도는 O(sqrt(n))
- 간단하게 구현하면 한줄로도 충분하다
def is_prime_small(n): return n >= 2 and all(n % i != 0 for i in range(2, math.isqrt(n) + 1))
- 하지만 좀더 빠르게 하려면 홀수에 대해서만 나눠볼수 있다. teflib.numtheory.is_prime_small 에 구현
밀러-라빈 알고리즘
- 실질적으로는 n이 대충 10^6을 넘어갈때부터, 밀러-라빈 알고리즘을 쓰는것이 trial division 보다 빠르다.
- 기본적으로는 확률적인 알고리즘이다. 한개의 base에 대해서 테스트했을때, 합성수인데도 통과할 확률은 1/4 이하이다. 그래서 여러번의 테스트를 통해서 확률을 낮추게 된다. k번의 테스트를 거친다면, 합성수가 소수로 판정될 확률은 4^(-k) 이하로 줄어드므로, k=20 정도로 잡아주면 사용하기 충분하다
- 베이스를 조절해서 랜덤 요소를 아예 제거할수도 있다.
- 이론적으로는 2ln(n^2) 이하의 모든 수를 base로 해서 테스트하면 정확한 결과를 얻는다고 한다.
- ps범위에서는
- 32bit 범위의 정수들은 2, 7, 61 만을 base로 해서 테스트해도 100% 정확한 결과를 준다
- 64bit 범위의 정수들은 2, 325, 9375, 28178, 450775, 9780504, 1795265022 를 base로 테스트하는게 가장 최소의 base를 사용하는 방법이다
- 시간복잡도는 O(logn) 정도로 생각하면 된다.
- 위키피디아 등에 설명된 원래의 시간복잡도는 O(k*log^3(n)) 으로 표현된다 (k는 테스트 횟수이고, n은 테스트하려는 수). 이것은 n에 매우 큰 수가 들어올 것을 고려해서 곱셈의 시간복잡도를 O(log^2(n))으로 생각해서 나온 결과이고, ps에서는 빅인티저를 써야 한다고 명시되는 범위가 아닌 한 곱셈은 그냥 O(1)로 생각하기 때문에 로그제곱을 떼어내도 된다. 마찬가지로 이 범위 안에서는 k 역시 최대 7로 고정했기 때문에 상수취급해서 떼어버리고 생각할수 있다. 그러면 그냥 O(logn)이라고 생각해도 무방하다.
- 구현
- n이 10^6보다 작으면 trial division으로 푼다.
여러 수에 대해서 소수 판별
- 1~n까지의 모든 수에 대해서 소수 판별을 하는 것은, 그냥 소수 목록을 구하는 것과 동일하다
- 그냥 여러개의 수에 대해서 소수판별을 할때에도, 범위가 크면 그냥 각각에 대해서 밀러-라빈을 돌리는 것이 제일 낫다.
- Trial division 을 개선해서, sqrt(n_i) 이하의 모든 수로 나눠보는 것 대신에, sqrt(n_i)이하의 모든 소수들로만 나눠보는 방법도 생각해볼수 있기는 하다.
- N=max(n_i)라고 할때, 전처리로 sqrt(N) 이하의 모든 소수 목록을 구해놓고 나면, sqrt(n_i)이하의 모든 소수들로 나눠서 테스트할수 있다. sqrt(n_i)이하의 모든 소수의 갯수는 O(sqrt(n_i)/ln(sqrt(n_i)))이므로, 1개의 수를 테스트 하는데도 O(sqrt(n_i)/ln(sqrt(n_i))) 가 걸리는데, 이것은 여전히 큰 n에 대해서는 밀러-라빈보다 느리고 비효율적이다.. ㅠㅠ
ps/소수_판별.txt · 마지막으로 수정됨: 2023/03/31 08:13 저자 teferi
토론