Your question is Prime Number Check and Optimization. Start with the requirements on the right.
Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.
PTC Windchill validation tools may need to classify large numeric identifiers or generated values during automated QA checks. Implement an efficient function that determines whether a given integer is prime.
A prime number is an integer greater than 1 with exactly two positive divisors: 1 and itself. Your solution must support the complete unsigned 64-bit range and produce an exact result, not a probabilistic answer.
Implement is_prime(n), where n is an integer in the range 0 through 2^64 - 1. Return True if n is prime and False otherwise. The function must use deterministic Miller-Rabin testing with a fixed witness set that is valid for all unsigned 64-bit integers. Handle small values and even numbers before modular exponentiation.
def is_prime(n):