Miller-Rabin Primality Check
HardMathNumber Theory
Description
Given a non-negative integer n, return true if n is prime and false otherwise. n may be as large as 10^18, so use a deterministic Miller-Rabin variant with a sufficient set of witness bases.
Examples
Input:
n = 1Output:
falseExplanation:
By definition, 1 is not a prime number, so the answer is false.
Input:
n = 1000000007Output:
trueExplanation:
1000000007 is a well-known prime used in modular arithmetic, so the answer is true.
Input:
n = 1000000008Output:
falseExplanation:
1000000008 is even and greater than 2, hence composite, so the answer is false.
Constraints
- •
0 ≤ n ≤ 10¹⁸