تست اول بودن عدد

هر عددی مانند $n$ حداکثر بر یک عدد اول بزرگ‌تر از $\sqrt{n}$ بخش‌پذیر است. برای تجزیه عدد $n$ می‌توان عدد اول و توان آن را به ازای تمام اعداد اول کوچک‌تر از $\sqrt{n}$ به دست آورد. سپس اگر ضرب این اعداد برابر $n$ نشد آنگاه $n$ تقسیم بر ضرب این اعداد برابر یک عدد اول است که خود باید در تجزیه بیاید.

factorization.cpp

def factorization(n):
    ans = []
    p = 2
    while p * p <= n:
        if n % p == 0:
            cnt = 0
            while n % p == 0:
                n /= p
                cnt += 1
            ans.append((p, cnt))
        p += 1
    if n > 1:
        ans.append((n, 1))
    return ans