### Python Code to Generate or Check Prime Numbers For generating or checking prime numbers in Python, one can use various methods including simple trial division for smaller primes or more sophisticated algorithms like the Miller-Rabin test for larger candidates. Below is an implementation of both approaches. #### Simple Trial Division Method This method checks divisibility by all integers up to the square root of the number being tested: ```python import math def is_prime_trial_division(n): """Check if n is a prime using trial division.""" if n <= 1: return False if n == 2: return True if n % 2 == 0: return False limit = int(math.sqrt(n)) + 1 for divisor in range(3, limit, 2): if n % divisor == 0: return False return True ``` #### Miller-Rabin Primality Test The Miller-Rabin primality test provides a probabilistic way to determine whether a given number is likely to be prime. This approach is particularly useful when dealing with very large numbers where deterministic tests become impractical due to computational cost[^2]. ```python from random import randint def miller_rabin_test(n, k=5): """Perform Miller-Rabin primality test on integer n; accuracy determined by parameter k.""" # Handle small values directly. if n < 2: return False for p in [2, 3, 5]: if n < p * p: return True if n % p == 0: return False r, s = 0, n - 1 while s % 2 == 0: r += 1 s //= 2 for _ in range(k): a = randint(2, n - 1) x = pow(a, s, n) if x == 1 or x == n - 1: continue for _ in range(r - 1): x = pow(x, 2, n) if x == n - 1: break else: return False return True ``` Both functions provide mechanisms for determining if a number is prime but cater to different ranges and requirements regarding performance versus certainty.