满分题解Python

解题思路:

注意事项:

参考代码:

import random

import math

def is_prime(n):

    if n <= 1:

        return False

    elif n <= 3:

        return True

    elif n % 2 == 0:

        return False

    d = n - 1

    s = 0

    while d % 2 == 0:

        d //= 2

        s += 1

    bases = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]

    for a in bases:

        if a >= n:

            continue

        x = pow(a, d, n)

        if x == 1 or x == n - 1:

            continue

        for _ in range(s - 1):

            x = pow(x, 2, n)

            if x == n - 1:

                break

        else:

            return False

    return True

def pollards_rho(n):

    if n % 2 == 0:

        return 2

    if n % 3 == 0:

        return 3

    if n % 5 == 0:

        return 5

    while True:

        c = random.randint(1, n-1)

        f = lambda x: (pow(x, 2, n) + c) % n

        x, y, d = 2, 2, 1

        while d == 1:

            x = f(x)

            y = f(f(y))

            d = math.gcd(abs(x - y), n)

        if d != n:

            return d

def factor(n):

    factors = []

    for p in [2, 3, 5, 7, 11, 13, 17, 19]:

        while n % p == 0:

            factors.append(p)

            n //= p

        if n == 1:

            return factors

    if n > 1:

        if is_prime(n):

            factors.append(n)

        else:

            d = pollards_rho(n)

            factors += factor(d)

            factors += factor(n // d)

    return factors

n = int(input())

if n == 1:

    print(0)

else:

    factors = factor(n)

    print(len(set(factors)))