from math import *


def factorization(n):

    if n <= 3:

        return [n]

    s = floor(sqrt(n))

    k = s * s - s

    if s & 1:

        k *= s - 2

    else:

        k *= s - 3

    f = gcd(n, k)

    if f == 1 or f == n:

        return [n]

    return factorization(n // f) + factorization(f)


원리를 설명하자면

n을 어떤 자연수라고 놓자

n이 홀수라면 gcd(n, n - 1, n - 2) = 1

n이 짝수라면 gcd(n, n - 1, n - 3) = 1

이고

k = n * (n - 1) * (n - 3 또는 n - 2)

일때 k는 많은 소수들의 곱이다

f = gcd(n, k)

f는 높은 확률로 n의 인수이고

이것을 재귀적으로 정의하면 높은 확률로 소인수분해가 완료된다 기대 가능하다