Published by Dimitris Kougioumtzis · Updated
Use deterministic bases 2 and 3 for the bounded domain n ≤ 9999. This bound is part of the contract.
Decompose n-1 into an odd factor and a power of two, then seek strong compositeness witnesses through powers and repeated squaring.
When to use Miller–Rabin primality test
Learning witness-based bounded primality testing.
Choosing an alternative
Sieving answers many shared-limit queries; trial division provides a simple baseline.
Worked example: input and state changes
Example input
2047
These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.
Step 0: Initial state.
State at this checkpoint
{ "values": [ 2047, 0, 0, 0 ], "active": [] }Step 1: n−1 = 1023 × 2^1; state: n, odd part, exponent, witness value.
State at this checkpoint
{ "values": [ 2047, 1023, 1, 0 ], "active": [] }Step 2: Base 2: initial witness 1.
State at this checkpoint
{ "values": [ 2047, 1023, 1, 1 ], "active": [ 3 ] }Step 3: Base 3: initial witness 1565.
State at this checkpoint
{ "values": [ 2047, 1023, 1, 1565 ], "active": [ 3 ] }Step 4: 2047 is not prime within the validated bound.
State at this checkpoint
{ "values": [ 2047, 1023, 1, 1565 ], "active": [], "result": 0 }
Expected final state
2047 is not prime within the validated bound.
Complexity and input bounds
Family: Number theory. Time complexity: O(log n) modular multiplications per base.
Space complexity: O(1) bounded modular working state.
Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.
One integer from 0 to 9999.
The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.
Common mistakes and limitations
Bases two and three are used only for the supported n at most 9999; this is not general cryptographic primality testing.
Further reading
For background on algorithm analysis and the JavaScript function interface:
- MIT OpenCourseWare: algorithm design and analysis foundations
- MDN: JavaScript function parameters and return values
Editorial and testing approach · Browse all algorithm guides
Complete JavaScript implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | // Only for 0 ≤ n ≤ 9999. Bases 2 and 3 are deterministic in this bounded domain; products fit signed 32-bit integers. Returns 1 for prime, 0 otherwise. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation. function algorithm(n) { if (n < 2) { return 0; } if (n == 2 || n == 3) { return 1; } if (n % 2 == 0) { return 0; } let d = n - 1; let s = 0; while (d % 2 == 0) { d >>= 1; s++; } for (let baseValue = 2; baseValue <= 3; baseValue++) { let x = 1; let b = baseValue % n; let power = d; while (power > 0) { if (power % 2 == 1) { x = x * b % n; } b = b * b % n; power >>= 1; } if (x == 1 || x == n - 1) { continue; } let passed = 0; for (let r = 1; r < s; r++) { x = x * x % n; if (x == n - 1) { passed = 1; break; } } if (passed == 0) { return 0; } } return 1; } |
Source
The papers describe Miller and Rabin primality methods. The bounded two-base playground implementation and its 9999 input limit are not the general algorithms reproduced verbatim.
- Riemann's hypothesis and tests for primality
Gary L. Miller (1976). Research paper. - Probabilistic algorithm for testing primality
Michael O Rabin (1980). Research paper.