The problem
Return whether a whole number n is prime, for any n from 0 up to just below 3 × 10²⁴. The answer must always be right: no chance of error is allowed.
is_prime(97) # True
is_prime(561) # False: 3 · 11 · 17
is_prime(2047) # False: 23 · 89
Limits
- Trial division up to √n is far too slow for large n.
- Some tests ask about thousands of numbers at once.
- The numbers include composites built to fool weaker tests: Carmichael numbers, and numbers that pass the strong test for many bases.
Builds on HARD-5 Randomised algorithms.
Continue on a laptop
Practice runs Python in the browser and needs a keyboard and a wider screen. Read the problem and open hints here, then write your solution on a laptop. Progress is saved per browser for now, so hints opened here stay on this device.
Need a hint?0 of 3 opened
- Hint 1Nudge
- Hint 2Approach Open hint 1 first
- Hint 3Pseudocode Open hint 2 first
- Worked solutionlast resort Opens after all 3 hints
Ctrl + Enter runs the tests. Tab indents; press Esc, then Tab, to leave the editor.
13 tests, not run yet
| # | Test | Result | Reads · time |
|---|---|---|---|
| 1 | Small numbers | Not run | |
| 2 | A Carmichael number | Not run | |
| 3 | More Carmichael numbers | Not run | |
| 4 | Fools base 2 | Not run | |
| 5 | Fools bases 2, 3, 5 and 7 | Not run | |
| 6 | Fools the first nine primes | Not run | |
| 7 | Fools the first twelve primes | Not run | |
| 8 | A big prime | Not run | |
| 9 | A square of a big prime | Not run | |
| 10 | Two prime factors near 10¹² | Not run | |
| 11 | Near 10²⁴ | Not run | |
| 12 | Primes near 10¹⁸ | Not run | |
| 13 | Primes below 200,000 | Not run |