Problem 3: Prime time

def is_prime(n): # deterministic Miller–Rabin primality‐test for any-size integer n # 0, 1, negatives if n < 2: return False # 2, 3 if n in (2, 3): return True # even numbers if n & 1 == 0: return False import math # write n − 1 as d·2^s with odd d d, s = n - 1, 0 while d & 1 == 0: d >>= 1 s += 1 def trial(a, d, s, n): x = pow(a, d, n) if x == 1 or x == n - 1: return True for _ in range(s - 1): x = pow(x, 2, n) if x == n - 1: return True return False # deterministic bases for numbers up to 2^64 small = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37) for a in small: if a % n == 0: # a ≥ n means n itself is in small return n == a if not trial(a, d, s, n): return False return True