취미로PS하는사람

https://www.acmicpc.net/problem/4149 큰 수를 소인수분해 해보자. 우선 밀러-라빈 알고리즘으로 해당 숫자가 소수인지 판별한 후 폴라드-로 알고리즘으로 소인수분해 하면 된다. 밀러-라빈 알고리즘은 검사하는 소수의 개수를 $k$, 소인수분해 하려는 수를 $n$이라 할 때 시간복잡도가 $O(k \log^3 {n})$이다. 자세한 사항은 위키백과를 참고하자. 참고로 $2^{64}$까지의 숫자를 결정론적으로 검사할 때는 $p = 2, 3, 5, ..., 37$이면 충분하다. 폴라드-로 알고리즘은 어떤 난수 발생 함수(이를테면 $f(x)=(x^2+1)\mod n$)가 $\mod n$에 대해 반복됨을 이용하는 것인데, 그 반복되는 주기가 $n$의 약수임을 이용한다. 자세한 내용은 나도 잘..