Prime Number Primality Checker

Prime Number Primality Checker

Growing AI Skill PRO

Enter Calculation

Enter a whole number greater than 1.

Formula

n=Number is prime⇔n>1∧∄d∈[2,⌊n⌋]:nmodd=0n = \text{Number} \text{ is prime} \iff n > 1 \;\wedge\; \nexists\, d \in [\,2,\ \lfloor\sqrt{n}\rfloor\,] : n \bmod d = 0
Usage stats

Advertisement

Results

Result for 91
composite
primality classification
Number 91
Factors 1, 7, 13, 91
Previous prime 89
Next prime 97

Report an error on this page

What is a prime number?

A prime number is a whole number greater than 1 that has exactly two positive divisors: 1 and itself. A composite number has more than two divisors. The number 1 is special: it has only one divisor, so it is neither prime nor composite. This calculator determines whether the number you enter is prime or composite, lists its factors, and shows the previous and next prime numbers.

Which prime number tool do you need?

  • Prime number checker (this page): whether a number is prime, with the previous and next prime.
  • Prime number calculator: whether a number is prime and its smallest factor other than 1.
  • Nth prime: the nth prime, or a list of the first N primes.
  • Prime factorization: the prime factors of a number, with a factor tree.
  • Relatively prime: whether two numbers are coprime (no common factor other than 1).
Comparison of a prime number arranged as a single row of dots versus a composite number arranged as a rectangular grid of dots
A prime number cannot form a rectangle of dots, while a composite number can.

How to use it

Type a whole number greater than 1 into the field and submit. The tool classifies it as prime or composite, restates the number, lists all its factors (for composites), and reports the largest prime below it and the smallest prime above it.

Advertisement

The formula explained

We use deterministic trial division with the 6k±1 optimization. First we rule out 2 and 3 as known primes and reject even numbers and multiples of 3. Then we test only candidate divisors of the form \(6k-1\) and \(6k+1\) (5, 7, 11, 13, ...) up to the square root of \(n\). If none divides \(n\) evenly, \(n\) is prime. We only need to test up to the square root because any factor larger than the square root pairs with one smaller than it.

$$n = \text{Number} \text{ is prime} \iff n > 1 \;\wedge\; \nexists\, d \in [\,2,\ \lfloor\sqrt{n}\rfloor\,] : n \bmod d = 0$$

Diagram showing trial division checking divisors only up to the square root of n
Trial division only needs to test divisors from 2 up to the square root of n.

Worked example

Take \(n = 97\). Its square root is about \(9.85\). It is odd and not a multiple of 3. We test 5 (\(97 \bmod 5 = 2\)) and 7 (\(97 \bmod 7 = 6\)). The next candidate is 11, but \(11 \times 11 = 121 > 97\), so we stop. No divisor was found, so 97 is prime. The previous prime is 89 and the next prime is 101.

Prime vs Composite: Example Inputs Compared

The table shows how the trial-division test treats seven inputs. The square-root bound is \(\lfloor\sqrt{n}\rfloor\), the largest divisor that must be tried. If no integer from 2 up to that bound divides \(n\), then \(n\) is prime. The previous and next primes are the nearest primes strictly below and above \(n\).

Input n Status All factors Previous prime Next prime Square-root bound \(\lfloor\sqrt{n}\rfloor\)
2 Prime 1, 2 none 3 1 (no divisors to try; 2 is the only even prime)
9 Composite 1, 3, 9 7 11 3 (3 divides 9)
15 Composite 1, 3, 5, 15 13 17 3 (3 divides 15)
49 Composite 1, 7, 49 47 53 7 (7 divides 49)
91 Composite 1, 7, 13, 91 89 97 9 (7 divides 91)
97 Prime 1, 97 89 101 9 (2, 3, 5, 7, 9 all fail to divide 97)
121 Composite 1, 11, 121 113 127 11 (11 divides 121)

Composites that look prime: 49, 91, and 121 are easy to mistake for primes because they are odd and not divisible by 3 or 5.

  • \(49 = 7 \times 7\)
  • \(91 = 7 \times 13\)
  • \(121 = 11 \times 11\)

Each has a divisor at or below its square-root bound, so checking only 2, 3, and 5 would wrongly call them prime. In contrast, 97 has no divisor up to 9, so it is prime.

Advertisement

Key Terms and Definitions

Prime
A whole number greater than 1 whose only positive divisors are 1 and itself (for example 2, 3, 5, 7, 97).
Composite
A whole number greater than 1 that has at least one divisor other than 1 and itself (for example 9, 49, 91). The numbers 0 and 1 are neither prime nor composite.
Factor / divisor
A whole number \(d\) that divides \(n\) with no remainder. For 15 the factors are 1, 3, 5, 15.
Modulo (mod)
The remainder after division. \(n \bmod d = 0\) means \(d\) divides \(n\) exactly. For example, \(91 \bmod 7 = 0\) but \(97 \bmod 7 = 6\).
Square root bound
If \(n = a \times b\) with \(a \le b\), then \(a \le \sqrt{n}\). So any composite number has a divisor between 2 and \(\lfloor\sqrt{n}\rfloor\), and testing beyond that is unnecessary.
Trial division
A primality test that divides \(n\) by candidate divisors from 2 up to \(\lfloor\sqrt{n}\rfloor\). If any division leaves remainder 0, \(n\) is composite; otherwise it is prime. It is simple and reliable, and it is fast for moderately sized numbers.
6k±1 form
Every prime greater than 3 can be written as \(6k-1\) or \(6k+1\) for some integer \(k\), because the other residues mod 6 are divisible by 2 or 3. This lets a test skip about two thirds of candidate divisors. The converse is false: 25, 35, 49, and 91 have this form but are composite.
Twin primes
Two primes that differ by 2, such as (3, 5), (11, 13), (17, 19), and (41, 43). Whether infinitely many twin prime pairs exist is an open question in mathematics.

Conventions and edge cases

Each case below was run through this calculator; the result column is what it actually returns.

CaseInputResult
Is 1 prime?1neither prime nor composite
Is 2 prime?2prime
Is 0 prime?0invalid

Checked on 2026-11-08

FAQ

Is 1 a prime number? No. 1 has only one divisor, so it is neither prime nor composite.

Is 2 prime? Yes. 2 is the smallest prime and the only even prime. It has no previous prime.

Why list factors only for composites? A prime by definition has only 1 and itself as factors, so the tool simply states that. Composites can have many factors, which are listed in ascending order.

Last updated:

Most popular in Math and Statistics

View all Math and Statistics calculators