新未名空间

代码： 全选

import math
#import sympy
#import random

def is_prime_miller_riemann(n):
    if n % 2 == 0:
        return False
    d = n - 1
    s = 0
    while d % 2 == 0:
        d //= 2
        s += 1
    for a in range(2, min(n - 2, int(2 * math.log(n)**2)) + 1):
        x = pow(a, d, n)
        for _ in range(s):
            y = pow(x, 2, n)
            if y == 1 and x != 1 and x != n - 1:
                # x是1的非平凡模n平方根，提前终止
                return False
            x = y
        if y != 1:
            # 费马测试失败，提前终止
            return False
    return True

result = is_prime_miller_riemann(10000002039473)  # True 
print(result)