How to Check if a Number Is Prime: 4 Easy Methods

Is 91 prime? Most people guess yes — it is odd, it does not end in 5, and it feels prime. But 91 is 7 × 13. Spotting primes quickly is a satisfying skill for students, puzzle fans and programmers alike, and it rests on a few elegant ideas that are more than two thousand years old. Here are four methods, from mental shortcuts to code, with examples you can try straight away.

Method 1: divisibility shortcuts

A prime has exactly two divisors: 1 and itself. So the fastest test is to rule out small divisors with mental rules:

• 2: the last digit is even.
• 3: the sum of the digits is divisible by 3 (for 471: 4 + 7 + 1 = 12, so 471 = 3 × 157).
• 5: the last digit is 0 or 5.
• 7: double the last digit and subtract it from the rest; repeat until the result is small (for 91: 9 − 2 = 7, so 91 is divisible by 7).
• 11: the alternating sum of the digits is divisible by 11 (for 286: 2 − 8 + 6 = 0).

These rules quickly eliminate most composite numbers you will meet in homework.

Method 2: trial division up to the square root

If a number n has a factor larger than its square root, the matching factor must be smaller than the square root. So you only need to test divisors up to √n, and only primes among them.

Example: is 221 prime? √221 is just under 15, so test 2, 3, 5, 7, 11 and 13. The first five fail, but 221 ÷ 13 = 17. So 221 is composite. For 223, none of those primes divide it, so 223 is prime — after only six divisions.

In code, the same idea looks like this: if n < 2 return false; then for d from 2 while d × d ≤ n, return false if n % d === 0; otherwise return true. Skipping even values of d after 2 halves the work.

Method 3: the Sieve of Eratosthenes

To find all primes up to a limit, the Greek scholar Eratosthenes described a beautiful method more than two thousand years ago:

1. Write the numbers from 2 to your limit, for example 100.
2. Circle 2, then cross out every multiple of 2.
3. Move to the next number not crossed out (3), circle it and cross out its multiples.
4. Repeat with 5 and 7. Once you pass the square root of the limit (10 for 100), every remaining number is prime.

You will end with 25 primes below 100. It makes a great hands-on classroom activity on a hundred chart, with a different color for each round.

Method 4: practice with random primes from RandNow

Checking methods is easier when you have a reliable answer key. The Random Prime Number Generator gives you one:

1. Set the Minimum and Maximum, anywhere from 2 to one billion. The default range gives primes below 1,000.
2. Choose how many primes you want, up to 100 per click. A narrow range may contain fewer primes than you request.
3. Generate; each result is checked for primality before it is shown.
4. Mix the primes with composite numbers from another list and challenge students to sort them using the methods above.
5. Copy, export as CSV, JSON or TXT, or press Enter or Space for a fresh set.

Why primes matter

Primes are the building blocks of whole numbers: every integer greater than 1 can be written as a product of primes in exactly one way, a result known as the fundamental theorem of arithmetic. Euclid proved that there are infinitely many of them.

They are also practical. Public-key systems such as RSA rely on the fact that multiplying two huge primes is easy, while recovering them from the product is extremely hard. Primes also appear in hash table sizes, random number algorithms and even in the life cycles of some periodical cicadas, which emerge every 13 or 17 years.

Open questions remain, too. Nobody has proved whether there are infinitely many twin primes — pairs like 11 and 13 that differ by 2 — or whether every even number greater than 2 is the sum of two primes, the famous Goldbach conjecture.

Pro tips

• Memorize the primes below 50; they cover most mental checks you will need.
• Always test 2, 3 and 5 first — they catch the majority of composite numbers.
• Watch out for “prime-looking” numbers such as 51, 57, 91 and 119.
• In code, use a sieve when you need many primes and trial division for a single check.

Frequently asked questions