Prime Numbers: Sieve, Factorization & PNT

Definition

Seven piles of tiles: 1, 2, 4, 7, 9, 11 and 12. Which of them can only be laid out as a single row?

Every pile can be laid as one long line. Some can also be arranged as a rectangle with two or more rows; others refuse.

Trying every rectangle settles it: 2, 7 and 11 allow only a single row; 4, 9 and 12 allow more.

tiles	rectangle layouts	positive divisors	only a single row?
1	1 × 1	1	one tile — a special case
2	1 × 2	1, 2	yes
4	1 × 4, 2 × 2	1, 2, 4	no
7	1 × 7	1, 7	yes
9	1 × 9, 3 × 3	1, 3, 9	no
11	1 × 11	1, 11	yes
12	1 × 12, 2 × 6, 3 × 4	1, 2, 3, 4, 6, 12	no

4, 9 and 12 have extra layouts because they split into smaller factors: 4 = 2 · 2, 9 = 3 · 3, 12 = 3 · 4.

Each extra rectangle is an extra pair of divisors. The single-row piles have exactly two divisors,

1

and the number itself — while

1

is the odd one out, with only one divisor.

The definition

A prime number is an integer greater than

1

whose only positive divisors are

1

and itself; an integer greater than

1

with more divisors is composite.

A prime number is an integer greater than

1

whose only positive divisors are

1

and itself. A composite number is an integer greater than

1

that has at least one positive divisor other than

1

and itself. Every integer greater than

1

is exactly one of these two types.

So

2

,

7

and

11

are prime;

4

,

9

and

12

are composite; and

1

is neither.

The primes form a sequence of their own, with no simple formula for the next one.

The first primes are:

Definition

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, \ldots

THEOREM

The number

2

is the only even prime — every other even number is divisible by

2

and therefore composite.

1 is not a prime — and that is a deliberate choice.

The number

1

is neither prime nor composite: it has exactly one positive divisor (itself), while primes are required to have exactly two.

The exclusion of

1

is not arbitrary. If

1

were prime, the fundamental theorem of arithmetic would fail:

12

could be factored as

2^2 \cdot 3

or

1 \cdot 2^2 \cdot 3

or

1^5 \cdot 2^2 \cdot 3

, and uniqueness of prime factorization would be lost.

Whether the primes ever run out is answered in infinitude of primes.

The rest of the page covers why there are infinitely many primes, the sieve of Eratosthenes, primality testing, prime factorization, the prime number theorem, and types of primes.

Prime Number Notation

Notation

Prime Number Notation

A letter that promises a prime, subscripts that list primes in two different senses, and a function named like the constant it is not.

Divisibility and

\gcd

follow divisibility notation and GCD notation;

\ln n

follows logarithm notation.

p

p — a prime

The standing letter for a prime: in a statement about

p

, only primes are meant. Composite numbers usually get

n

or

m

.

Cases

2

is the only even value

p

can take;

1

is never a

p

.

Do not confuse

p

as a probability or a polynomial — outside number theory, the letter promises nothing.

p_1, p_2, \ldots, p_k

p sub one up to p sub k

Subscripts name primes in order. In Euclid's proof the list is every prime there is, assumed finite:

N = p_1 p_2 \cdots p_k + 1

.

CasesIn a factorization

n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}

the same letters list only the primes of

n

, each with its exponent (section 5).

Do not confuseThe two readings. In a factorization

p_1

is the smallest prime of

n

, not necessarily

2

: for

1001 = 7 \cdot 11 \cdot 13

,

p_1 = 7

.

\pi(n)

pi of n — the number of primes up to n

The prime-counting function:

\pi(10) = 4

,

\pi(100) = 25

. The prime number theorem says

\pi(n) \approx \frac{n}{\ln n}

.

CasesCounts primes less than or equal to

n

:

\pi(7) = 4

includes

7

itself.

Also written

\pi(x)

— with a real input, a step function that jumps by

1

at each prime.

Same glyph elsewhere

\pi \approx 3.14159

, the circle constant — unrelated. The parentheses are the only signal:

\pi(n)

is a count,

\pi n

a product.

All algebra symbols →↑ Sequences

DownloadPNG2×PDF

Notation · Cheat sheet

Sequence Notation at a Glance

The marks from the notation cards across the sequence pages: how each is read and what it means. Every group links to the full card on its page.

Sequences

a_n

a sub n

The term in place

n

; the subscript is a position.

a_1, a_2, a_3, \ldots

a one, a two, a three, and so on

The terms listed in order; the dots need a stated rule.

\{a_n\}_{n=1}^{\infty}

the sequence a sub n

The whole sequence as one object.

Arithmetic sequences

a_{n+1} = a_n + d

next term is this term plus d

The recurrence;

d

is the common difference,

a_1

the start.

\textstyle\sum_{k=1}^{n} a_k

sum of a sub k, k from 1 to n

Sigma: the sum

S_n

of the first

n

terms.

Geometric sequences

r

r, the common ratio

The factor from each term to the next:

a_n = a_1 r^{n-1}

.

S_n

S sub n

Sum of the first

n

terms;

n

counts terms.

S

S, the infinite sum

Equals

a_1 / (1 - r)

, only when

|r| < 1

.

G

G, the geometric mean

G = \sqrt{ab}

, the middle value of

a, G, b

.

Fibonacci sequence

F_n

F sub n

The

n

-th Fibonacci number, counted from

F_1 = F_2 = 1

.

\phi, \; \psi

phi and psi

The roots of

x^2 = x + 1

, about

1.618

and

-0.618

.

L_n

L sub n

Lucas numbers: the same rule, started at

1, 3

.

Harmonic sequences

a_n = 1/b_n

a sub n is one over b sub n

b_n

is the arithmetic sequence underneath.

H_n

H sub n

The harmonic number

1 + \frac{1}{2} + \cdots + \frac{1}{n}

.

H

H, the harmonic mean

For two numbers,

H = \frac{2ab}{a + b}

.

Triangular numbers

T_n

T sub n

The

n

-th triangular number,

\frac{n(n+1)}{2}

.

T_n = T_{n-1} + n

the one before plus a row of n

The recurrence, from

T_1 = 1

.

\binom{n+1}{2}

n plus one choose two

The same number, counted as pairs.

Square numbers

S_n = n^2

S sub n on this page

The

n

-th square: one term, not a sum.

S_n = S_{n-1} + 2n - 1

the one before plus the next odd number

The recurrence, from

S_1 = 1

.

\textstyle\sum_{k=1}^{n} k^2

sum of k squared

Square each term first, then add.

Prime numbersThis page

p

p, a prime

The letter promises a prime.

p_1, \ldots, p_k

p sub one to p sub k

A list of primes, or the primes of one number.

\pi(n)

pi of n

How many primes are at most

n

.

Same letter, different job

S_n

A sum of

n

terms on the arithmetic and geometric pages; a single square on the square numbers page.

H_n

vs

H

With a subscript, a sum of reciprocals; without one, a mean.

\pi(n)

vs

\pi

A count of primes, not the circle constant.

\{a_n\}

An ordered sequence, not a set: terms keep their order and may repeat.

Sequence symbols table Sequences

Sequence Notation at a Glance·/algebra/sequencesLearn Math Class

Infinitude of Primes

THEOREM

There are infinitely many prime numbers.

Euclid's proof, over two thousand years old, is one of the most celebrated arguments in all of mathematics.

Assume, for contradiction, that only finitely many primes exist:

p_1, p_2, \ldots, p_k

. Form the number:

Infinitude of Primes

N = p_1 \cdot p_2 \cdot p_3 \cdots p_k + 1

Dividing

N

by any prime

p_i

on the list leaves a remainder of

1

, so

N

is not divisible by any of the listed primes. Either

N

is itself prime (a prime missing from the list) or

N

has a prime factor not on the list. In either case, the original list is incomplete.

The argument does not claim that

N

is prime — it claims that

N

has a prime factor outside the assumed list. For instance,

2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30031 = 59 \cdot 509

, which is composite, but its factors

59

and

509

are primes not in the original set.

No finite collection of primes can account for all of them. New primes always exist beyond any boundary.

The Sieve of Eratosthenes

The sieve of Eratosthenes is a systematic algorithm for finding all primes up to a given limit

n

.

Start with a list of integers from

2

to

n

. The smallest unmarked number is

2

— it is prime. Cross out every multiple of

2

(i.e.,

4, 6, 8, 10, \ldots

). The next unmarked number is

3

— it is prime. Cross out every multiple of

3

that has not already been crossed out (

9, 15, 21, \ldots

; note

6, 12, 18

are already gone). Continue: the next unmarked number is

5

, cross out its multiples, and so on.

The process stops once the current prime exceeds

\sqrt{n}

. Any composite number

\leq n

must have a factor

\leq \sqrt{n}

, so if it were not already eliminated, one of its factors would have crossed it out in an earlier pass.

Pitfall: Counting 1 as a prime

Starting the list at

1

leaves

1

standing, since it is not a multiple of any prime, and the count up to

30

comes out as

11

. The list starts at

2

because

1

is not prime: there are

10

primes up to

30

.

Primality Testing

To determine whether a single integer

n

is prime, the most direct method is trial division: test whether

n

is divisible by any integer from

2

to

\lfloor \sqrt{n} \rfloor

.

The bound

\sqrt{n}

is sufficient because if

n = ab

with

a \leq b

, then

a \leq \sqrt{n}

. Any factor at or below the square root will be caught; any factor above it has a complementary factor below it.

Efficiency improves by skipping even numbers after checking

2

: if

n

is not divisible by

2

, it cannot be divisible by

4, 6, 8, \ldots

. Checking only

2

and odd numbers up to

\sqrt{n}

cuts the work roughly in half. Further savings come from checking only

2, 3

, and numbers of the form

6k \pm 1

, since every prime greater than

3

has this form.

Example

Is

97

prime?

\sqrt{97} < 10

, so check divisibility by

2, 3, 5, 7

. None divide

97

, so it is prime.

Example

Is

91

prime? Check

2

(no),

3

(no),

5

(no),

7

:

91 = 7 \times 13

. It is composite.

Pitfall: Stopping the trial division too early

Testing only

2, 3, 5, 7

and calling

143

prime stops short of

\sqrt{143} \approx 11.96

. Testing

11

as well gives

143 = 11 \cdot 13

, composite.

Prime Factorization

The fundamental theorem of arithmetic states that every integer greater than

1

can be expressed as a product of prime numbers, and this factorization is unique up to the order of the factors.

Prime Factorization

60 = 2^2 \cdot 3 \cdot 5, \quad 360 = 2^3 \cdot 3^2 \cdot 5, \quad 1001 = 7 \cdot 11 \cdot 13

No matter how the factorization is carried out — whether starting by dividing out

2

s or by noticing that

1001 = 7 \times 143

— the final set of prime factors and their multiplicities is always the same.

Finding the factorization uses repeated division by the smallest available prime. Divide

n

by

2

as many times as possible, then by

3

, then by

5

, and so on.

Example

For

252

:

252 \div 2 = 126

,

126 \div 2 = 63

,

63 \div 3 = 21

,

21 \div 3 = 7

, and

7

is prime. So

252 = 2^2 \cdot 3^2 \cdot 7

.

Prime factorization connects directly to the GCD and LCM.

RULE

Given the factorizations of two numbers, the GCD takes the minimum power of each shared prime, and the LCM takes the maximum power of each prime that appears in either factorization.

Pitfall: Using the larger powers for the GCD

Taking the larger exponents of the shared primes gives

\gcd(60, 252) = 2^2 \cdot 3^2 = 36

, which does not even divide

60

. The GCD takes the smaller ones,

2^2 \cdot 3 = 12

; the larger powers of all primes give the LCM,

1260

.

The Prime Number Theorem

Although primes are infinite, they become rarer among larger integers. Among the first

100

integers,

25

are prime. Among the first

1{,}000

, only

168

. Among the first

1{,}000{,}000

, only

78{,}498

.

The prime number theorem makes this thinning precise. Let

\pi(n)

denote the number of primes less than or equal to

n

. Then:

Prime Number Theorem

\pi(n) \approx \frac{n}{\ln n}

Learn more about this formula: Prime Number Theorem →

Browse all algebra formulas →

as

n

grows large. The approximation improves in relative terms: the ratio

\frac{\pi(n)}{n / \ln n}

approaches

1

.

Fact: A hundred composites in a row

The numbers

101! + 2, 101! + 3, \ldots, 101! + 101

are

100

consecutive composites, because

k

divides

101! + k

for every

k

from

2

to

101

. The same trick gives a prime-free run of any length.

The practical interpretation is that near a large number

n

, roughly one in every

\ln n

integers is prime. Near

n = 1{,}000{,}000

, the average gap between consecutive primes is about

\ln(10^6) \approx 13.8

. Near

n = 10^{12}

, it is about

27.6

. Primes spread further apart on average but never disappear.

The prime number theorem was conjectured by Gauss and Legendre in the late 18th century and proved independently by Hadamard and de la Vallée-Poussin in 1896.

Counting primes up to 100

The blue steps are π(n): the count goes up by 1 at each prime 2, 3, 5, 7, …, 97 and reaches 25 at n = 100. The dashed curve is the estimate n / ln n, which gives about 21.7 there. The steps get longer as n grows because primes spread out; the curve follows that bend, and the ratio of the two tends to 1 as n grows without bound.

Below 100 the estimate runs low by about 3; in relative terms the gap shrinks as n grows.

Primes never run out, but they thin out at a steady rate: near

n

, about one integer in

\ln n

is prime.

Types of Primes

Certain primes satisfy additional structural constraints, leading to named families.

Mersenne primes have the form

2^p - 1

, where

p

itself must be prime (though not every prime

p

produces a Mersenne prime). The first Mersenne primes are

3, 7, 31, 127

(corresponding to

p = 2, 3, 5, 7

). The exponent

p = 11

gives

2^{11} - 1 = 2047 = 23 \times 89

, which is composite. The largest known primes are typically Mersenne primes, found by specialized search algorithms.

Fact: Why a 17-gon can be drawn

A regular polygon with a prime number

p

of sides can be drawn with ruler and compass exactly when

p - 1

is a power of

2

, that is, when

p

is a Fermat prime. So the

17

-gon, found by Gauss at

18

, can be drawn, but the

7

-gon cannot.

Fermat primes have the form

2^{2^n} + 1

. Only five are known:

3, 5, 17, 257, 65537

(for

n = 0, 1, 2, 3, 4

). Fermat conjectured that all numbers of this form are prime; Euler disproved this by showing

2^{2^5} + 1 = 4294967297 = 641 \times 6700417

.

Twin primes are pairs of primes that differ by

2

:

(3, 5)

,

(5, 7)

,

(11, 13)

,

(17, 19)

,

(29, 31)

. Whether infinitely many twin prime pairs exist remains one of the oldest open problems in mathematics — the twin prime conjecture is widely believed true but unproven.

Sophie Germain primes are primes

p

for which

2p + 1

is also prime. The first examples are

2, 3, 5, 11, 23, 29, 41

. These primes play a role in primality testing algorithms and in the theory of safe primes used in cryptography.

DownloadPNG2×PDF

Before you read

Named families of primes

Some primes follow a pattern special enough to earn a name. Four families come up again and again.

Types of primes4 families

Mersenne

2^p - 1

,

p

prime

Examples3, 7, 31, 127

Notethe largest known primes

$2^{11} - 1$ is composite

Fermat

2^{2^n} + 1

Knownonly five: 3 up to 65537

Euler disproved the conjecture

Twin

p

,

p + 2

Open questionare there infinitely many?

Sophie Germain

p

and

2p + 1

prime

Used incryptography (safe primes)

Takeaway

Patterns, not guarantees

A formula that produces primes for small inputs can fail later:

2^{11} - 1

is composite, and Euler disproved the Fermat conjecture.

Named families of primes·/algebra/sequences/prime-numbersLearn Math Class

Common Pitfalls

Three mistakes come up again and again with prime numbers. Each one is marked where it happens in the sections above; here each is worked through in full, with the wrong and the right working side by side.

DownloadPNG2×PDF

1Counting 1 as a prime

When primes are listed or counted,

1

is included with them. In the sieve this happens when the list starts at

1

instead of

2

:

1

is not a multiple of any prime, so no pass ever crosses it out.

Wrong turn

Error here

Sieve the list

1, 2, 3, \ldots, 30

by

2

,

3

and

5

. The survivors are

1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29

And the count of primes up to

30

comes out as

11

.

Right path

A prime has exactly two positive divisors, and

1

has only one, so the list starts at

2

. The survivors are

2, 3, 5, 7, 11, 13, 17, 19, 23, 29

Which is

10

primes. In the same way

\pi(100) = 25

, not

26

.

Why it happensThe short form of the definition, "divisible only by

1

and itself", seems to fit

1

, since its only divisor is both

1

and itself. The requirement of two different divisors gets lost.

How to checkCount the divisors. A prime has exactly two;

1

has one. A count can be tested on a small case:

\pi(10) = 4

, for the primes

2, 3, 5, 7

.

2Stopping the trial division too early

Trial division stops at a fixed list of small primes, often

2, 3, 5, 7

from familiar examples, instead of running through every prime up to

\sqrt{n}

. A number with no small factor is then declared prime.

Wrong turn

Error here

143

is odd, its digit sum

8

is not a multiple of

3

, it does not end in

0

or

5

, and

143 = 7 \cdot 20 + 3

. No divisor among

2, 3, 5, 7

, so

143

is called prime.

Right path

\sqrt{143} \approx 11.96

, so the primes to test are

2, 3, 5, 7, 11

. The last one divides:

143 = 11 \cdot 13

And

143

is composite.

Why it happensThe examples with

91

and

97

end at

7

, and that list is easy to reuse without working out the bound again. The same slip appears at a perfect square: for

49

, testing only the primes below

7

misses

7 = \sqrt{49}

, and

49 = 7 \cdot 7

.

How to checkFind the bound first. The last prime to test is the largest prime

p

with

p^2 \leq n

. For

143

,

11^2 = 121 \leq 143

while

13^2 = 169 > 143

, so

11

must be on the list.

3Using the larger powers for the GCD

When the GCD and LCM are read from prime factorizations, the two rules are swapped: the GCD gets the larger power of each shared prime, or the LCM gets the smaller ones.

Start

For

60 = 2^2 \cdot 3 \cdot 5

and

252 = 2^2 \cdot 3^2 \cdot 7

,

Wrong turn

Error here

\gcd(60, 252) = 2^2 \cdot 3^2 = 36

Right path

The GCD takes the smaller exponent of each shared prime, and the LCM takes the larger exponent of every prime that appears in either number.

\gcd(60, 252) = 2^2 \cdot 3 = 12,

\text{lcm}(60, 252) = 2^2 \cdot 3^2 \cdot 5 \cdot 7 = 1260

Why it happensThe word "greatest" in greatest common divisor suggests taking the greatest exponents. But a divisor of both numbers cannot hold more copies of a prime than the number that has the fewest.

How to checkThe GCD must divide both numbers.

60 \div 36

is not a whole number, while

60 \div 12 = 5

and

252 \div 12 = 21

. A second check: the GCD times the LCM equals the product of the two numbers,

12 \cdot 1260 = 15120 = 60 \cdot 252

.

Common pitfalls with prime numbers·/algebra/sequences/prime-numbersLearn Math Class

Each slip loosens a definition. A prime has exactly two divisors, so

1

is not one; trial division must reach the largest prime whose square does not exceed the number; and the GCD takes the smaller exponent of each shared prime, the LCM the larger. A small test settles each case: count the divisors, square the last prime tested, or check that the GCD divides both numbers.

Prime Numbers FAQ

Is $2^p - 1$ prime whenever $p$ is prime?

+

No, and this is the standard trap with Mersenne numbers. A prime exponent is necessary but not sufficient:

p = 2, 3, 5, 7

give the primes

3, 7, 31, 127

, but

p = 11

gives

2^{11} - 1 = 2047

, which factors as

23 \times 89

. Mersenne primes still supply the largest primes known, found by dedicated search.Read more →

Was Fermat right that every $2^{2^n} + 1$ is prime?

+

No. Fermat conjectured it after checking

n = 0

through

4

, which give

3, 5, 17, 257

and

65537

. Euler then factored the next one:

2^{2^5} + 1 = 4294967297 = 641 \times 6700417

. Those five remain the only Fermat primes anyone has found, so the conjecture failed at the first case beyond hand computation.Read more →

Are there infinitely many twin primes?

+

Nobody knows, and it is one of the oldest open problems in mathematics. Twin primes are pairs differing by

2

, such as

(11, 13)

and

(29, 31)

, and they keep appearing as far as anyone has searched. That contrasts sharply with primes themselves, where infinitude was proved in antiquity. The twin prime conjecture is widely believed but unproven.Read more →

Is $p_1 p_2 \cdots p_k + 1$ always prime?

+

No, and Euclid's proof never claims it is. The number

N = p_1 p_2 \cdots p_k + 1

leaves remainder

1

on division by each listed prime, so its prime factors lie outside the list, but

N

itself can be composite. The primes up to

13

give

2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30031 = 59 \cdot 509

. The smaller cases

3, 7, 31, 211, 2311

happen to be prime, which is why the claim looks plausible.Read more →

Is every number of the form $6k \pm 1$ prime?

+

No; the rule only runs one way. Every prime greater than

3

has the form

6k \pm 1

, because

6k

,

6k + 2

and

6k + 4

are even and

6k + 3

is a multiple of

3

. But many numbers of that form are composite, such as

25 = 6 \cdot 4 + 1

and

35 = 6 \cdot 6 - 1

. The form shortens the list of trial divisors; it does not replace trial division.Read more →

Can gaps between primes be as long as you like?

+

Yes. The numbers

101! + 2, 101! + 3, \ldots, 101! + 101

are

100

consecutive composites, because each

k

from

2

to

101

divides both

101!

and

k

, and therefore divides

101! + k

. Replacing

101

by a larger number gives a longer run. This fits the prime number theorem: near

n

the average gap between primes is about

\ln n

, which grows without bound.Read more →

Why can a regular 17-gon be drawn with ruler and compass but not a 7-gon?

+

Because

17

is a Fermat prime and

7

is not. A regular polygon with a prime number

p

of sides can be constructed with ruler and compass exactly when

p - 1

is a power of

2

, which makes

p

a Fermat prime

2^{2^n} + 1

. Here

17 - 1 = 16 = 2^4

, while

7 - 1 = 6

is not a power of

2

. Gauss found the

17

-gon construction at

18

.Read more →

Prime Numbers

Integers with Exactly Two Factors

Definition

Prime Number Notation

Prime Number Notation

Infinitude of Primes

The Sieve of Eratosthenes

Primality Testing

Prime Factorization

The Prime Number Theorem

Types of Primes

Common Pitfalls

Prime Numbers FAQ

Is 2p−12^p - 12p−1 prime whenever ppp is prime?

Was Fermat right that every 22n+12^{2^n} + 122n+1 is prime?

Are there infinitely many twin primes?

Is p1p2⋯pk+1p_1 p_2 \cdots p_k + 1p1​p2​⋯pk​+1 always prime?

Is every number of the form 6k±16k \pm 16k±1 prime?

Can gaps between primes be as long as you like?

Why can a regular 17-gon be drawn with ruler and compass but not a 7-gon?

Is $2^p - 1$ prime whenever $p$ is prime?

Was Fermat right that every $2^{2^n} + 1$ is prime?

Is $p_1 p_2 \cdots p_k + 1$ always prime?

Is every number of the form $6k \pm 1$ prime?