Prime Numbers: Testing & Ranges

Prime numbers are positive integers greater than 1 that have exactly two positive factors:

1 and the number itself

Examples include:

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

A number greater than 1 that is not prime is composite.

For example:

17

has only the factors:

1 and 17

so 17 is prime.

But:

18

has factors such as:

1, 2, 3, 6, 9, 18

so it is composite.

A practical primality test does not require trying every integer below a candidate. For an integer n > 1, it is enough to test possible prime divisors up to:

√n

If none divides n, then n is prime.

This square-root rule is the foundation of efficient hand testing and many basic prime-number algorithms.

What Is a Prime Number?

An integer p is prime when:

p > 1

and its only positive divisors are:

1 and p

Examples:

2

3

5

7

11

Each has exactly two positive factors.

Prime numbers act as the basic multiplicative building blocks of positive integers because every integer greater than 1 can be decomposed into primes through prime factorization.

What Is a Composite Number?

An integer greater than 1 is composite when it has a positive factor other than:

1

and:

itself

For example:

21 = 3 × 7

Therefore 21 is composite.

Likewise:

49 = 7²

so 49 is composite.

The distinction between prime and composite numbers covers every positive integer greater than 1.

Is 1 a Prime Number?

No.

The number 1 has only one positive factor:

1

A prime number must have exactly two distinct positive factors.

Therefore:

1 is neither prime nor composite

This convention is also necessary for unique prime factorization.

Is 0 Prime?

No.

Zero is divisible by every nonzero integer, so it does not have exactly two positive factors.

Therefore:

0 is neither prime nor composite

Are Negative Numbers Prime?

Under the standard elementary definition, prime numbers are:

positive integers greater than 1

So negative integers such as:

-2, -3, -5

are not called prime numbers in this convention.

Advanced algebra sometimes discusses prime elements up to multiplication by units, but ordinary integer primality uses positive numbers.

Is 2 Prime?

Yes.

The factors of 2 are:

1 and 2

Therefore:

2 is prime

It is also the only even prime number.

Every other even integer greater than 2 is divisible by:

2

and is therefore composite.

Why 2 Is the Only Even Prime

Any even integer can be written:

n = 2k

If:

n > 2

then:

k > 1

so n has factors:

1, 2, k, n

at minimum.

Therefore every even integer greater than 2 is composite.

That leaves:

2

as the unique even prime.

First Prime Numbers

The prime numbers below 100 are:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

There are:

25 primes below 100

These values are useful reference points for primality testing and factorization.

How to Test Whether a Number Is Prime

For an integer:

n > 1

a basic primality test is:

1. Check small obvious divisors such as 2, 3, and 5.
2. Compute or estimate √n.
3. Test only prime divisors not exceeding √n.
4. If none divides exactly, n is prime.

The key result is:

If n is composite, it has a factor ≤ √n

Therefore testing beyond the square root is unnecessary.

Why You Only Test Up to √n

Suppose n is composite.

Then:

n = ab

for integers:

1 < a < n

and:

1 < b < n

Assume both factors were greater than:

√n

Then:

a > √n

and:

b > √n

Multiplying gives:

ab > n

But:

ab = n

which is impossible.

Therefore at least one factor must satisfy:

a ≤ √n

That proves the square-root testing rule.

Example: Is 29 Prime?

Estimate:

√29 ≈ 5.39

Therefore only prime divisors up to 5 need testing:

2, 3, 5

29 is not divisible by 2.

Digit sum:

2 + 9 = 11

so it is not divisible by 3.

It does not end in 0 or 5, so it is not divisible by 5.

No prime divisor ≤ √29 works.

Therefore:

29 is prime

Example: Is 91 Prime?

Estimate:

√91 ≈ 9.54

Test primes up to 9.54:

2, 3, 5, 7

91 is odd.

Digit sum:

9 + 1 = 10

so it is not divisible by 3.

It does not end in 0 or 5.

Test 7:

91 ÷ 7 = 13

Therefore:

91 = 7 × 13

So:

91 is composite

Once one nontrivial factor is found, testing can stop.

Example: Is 97 Prime?

Estimate:

√97 ≈ 9.85

Test:

2, 3, 5, 7

97 is not even.

Digit sum:

9 + 7 = 16

so it is not divisible by 3.

It does not end in 0 or 5.

And:

97 ÷ 7

is not an integer.

Therefore:

97 is prime

There is no need to test 11 because:

11 > √97

Example: Is 121 Prime?

Estimate:

√121 = 11

Test prime divisors up through 11.

The number is not divisible by 2, 3, 5, or 7.

But:

121 ÷ 11 = 11

Therefore:

121 = 11²

So:

121 is composite

Testing must include a divisor equal to the square root.

Divisibility Tests Make Prime Checking Faster

Before performing full division, divisibility rules can eliminate many candidates quickly.

For example:

Divisible by 2: last digit is even.

Divisible by 3: digit sum is divisible by 3.

Divisible by 5: last digit is 0 or 5.

Divisible by 11: an alternating-digit test can often be used.

These shortcuts reduce the number of explicit divisions required.

Test 237 for Primality

Digit sum:

2 + 3 + 7 = 12

Since 12 is divisible by 3:

237

is divisible by 3.

Indeed:

237 ÷ 3 = 79

Therefore:

237 = 3 × 79

and:

237 is composite

There is no reason to continue testing after finding factor 3.

Test 221 for Primality

Estimate:

√221 ≈ 14.87

Prime candidates are:

2, 3, 5, 7, 11, 13

221 is odd.

Digit sum:

5

so not divisible by 3.

It does not end in 0 or 5.

Testing gives:

221 ÷ 13 = 17

Therefore:

221 = 13 × 17

so 221 is composite.

Test 223 for Primality

Estimate:

√223 ≈ 14.93

Test primes:

2, 3, 5, 7, 11, 13

223 is not divisible by any of them.

Therefore:

223 is prime

Trial Division

The method of testing possible divisors up to the square root is called trial division.

A simple optimized version tests:

2

then only odd numbers:

3, 5, 7, 9, 11, …

A better version tests only primes.

For hand calculations, prime trial division is usually efficient for modest-sized numbers.

For very large integers, more advanced primality tests are used.

Prime Factors vs. Prime Number Testing

Primality testing asks:

Does this number have any nontrivial factor?

Prime factorization asks:

What are all of its prime factors?

For example, testing:

84

for primality ends immediately when factor 2 is found.

Factorization continues:

84 = 2² × 3 × 7

Thus primality testing can stop after the first proper factor; factorization cannot.

Prime Numbers in a Range

Sometimes the task is not to test one number but to list all primes between two limits.

For example:

primes from 10 through 30

Test each candidate while eliminating obvious composites.

The primes are:

11, 13, 17, 19, 23, 29

Numbers such as:

12, 14, 16, 18, …

are even and composite.

Numbers such as:

15, 21, 27

are divisible by 3.

And:

25 = 5²

is composite.

Prime Numbers From 1 to 20

The primes are:

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

Remember:

1

is not prime.

There are:

8 primes from 1 through 20

Prime Numbers From 20 to 50

The primes are:

23, 29, 31, 37, 41, 43, 47

There are:

7

prime numbers in this interval.

Prime Numbers From 50 to 100

The primes are:

53, 59, 61, 67, 71, 73, 79, 83, 89, 97

There are:

10 primes from 50 through 100

Prime Counts as a Proportion of a Range

Prime density in a finite range can be described using a proportion.

For example, from integers:

1 through 20

there are:

8 primes

So the prime proportion is:

8/20

= 2/5

= 0.4

Thus:

40% of the integers from 1 through 20 are prime

This percentage describes that finite range only; it is not a universal percentage for all integers.

Comparing Prime Proportions Across Ranges

The broader idea of proportions can compare prime counts across similarly defined intervals.

For example:

From 1 through 10:

4 primes out of 10

From 1 through 100:

25 primes out of 100

The proportions are:

4/10 = 40%

and:

25/100 = 25%

Primes become less dense among larger integers, even though infinitely many primes exist.

Sieve Method for a Range

When many primes must be found within a range, repeatedly testing every number independently can duplicate work.

A classical range method proceeds by:

1. listing integers from 2 through the upper limit;
2. keeping 2 and crossing out its larger multiples;
3. keeping the next uncrossed number, 3, and crossing out its larger multiples;
4. continuing with the next uncrossed primes;
5. stopping the crossing process once the current prime exceeds the square root of the upper limit.

The remaining uncrossed integers are prime.

This method efficiently exploits the relationship between primes and multiples.

Example: Primes Up to 30

Start:

2 through 30

Keep:

2

Remove larger multiples of 2:

4, 6, 8, 10, …

Keep:

3

Remove larger multiples of 3:

6, 9, 12, 15, …

Keep:

5

Remove larger multiples of 5:

10, 15, 20, 25, 30

Since:

√30 ≈ 5.48

no larger prime needs to begin a new elimination pass.

The remaining values are:

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

Why Composite Numbers Get Eliminated

Every composite number has a prime factor.

For example:

77 = 7 × 11

So once multiples of 7 are removed, 77 disappears.

Likewise:

143 = 11 × 13

so it is removed by a prime-factor pass.

Range filtering works because every composite integer has at least one prime divisor.

Prime Gaps

The difference between consecutive primes is called a prime gap.

Examples:

2 → 3: gap 1

3 → 5: gap 2

5 → 7: gap 2

7 → 11: gap 4

23 → 29: gap 6

Except for:

2 and 3

all primes are odd, so later prime gaps are even.

Prime gaps are not constant, so the prime numbers do not form an arithmetic sequence.

Prime Numbers Are Not an Arithmetic Sequence

Consider:

2, 3, 5, 7, 11, 13, …

Differences:

1, 2, 2, 4, 2, …

They are not constant.

Therefore prime numbers do not form an ordinary arithmetic number sequence.

Their distribution follows more complicated number-theoretic patterns.

Every Prime Greater Than 3 Is 6k ± 1

Every integer can be written in one of six forms:

6k

6k + 1

6k + 2

6k + 3

6k + 4

6k + 5

If a prime is greater than 3, it cannot be divisible by 2 or 3.

The forms:

6k, 6k+2, 6k+4

are even.

The form:

6k+3

is divisible by 3.

Therefore primes greater than 3 must have form:

6k+1

or:

6k-1

because:

6k+5 = 6(k+1)-1

But 6k ± 1 Does Not Guarantee Primality

The condition is necessary, not sufficient.

For example:

25 = 6(4)+1

but:

25 = 5²

so it is composite.

Likewise:

35 = 6(6)-1

but:

35 = 5 × 7

Therefore 6k ± 1 is useful for eliminating candidates, not proving primality by itself.

Prime Numbers and Modular Arithmetic

The 6k ± 1 observation can be written using modular arithmetic:

For every prime:

p > 3

we must have:

p ≡ 1 or 5 (mod 6)

Since:

5 ≡ -1 (mod 6)

this is often written:

p ≡ ±1 (mod 6)

Again, many composite numbers satisfy the same residue condition.

Coprime Numbers Are Not Necessarily Prime

Two integers are coprime when their greatest common factor is 1.

For example:

8 and 15

are both composite, yet:

GCF(8,15) = 1

So they are coprime.

Prime and coprime are different concepts:

prime describes one integer’s factors;

coprime describes the factor relationship between two integers.

Prime Numbers and GCF

If p is prime and a is an integer not divisible by p, then:

GCF(p,a) = 1

For example:

GCF(7,20) = 1

But if p divides a, then:

GCF(p,a) = p

For example:

GCF(7,35) = 7

This simple either-or structure is one reason primes are fundamental in divisibility problems.

Prime Numbers and the Euclidean Algorithm

The Euclidean algorithm can determine whether two numbers are coprime without fully factoring them.

If:

GCF(a,b) = 1

they share no prime factor.

For example:

GCF(35,64) = 1

so no prime divisor occurs in both numbers.

This does not imply either number is prime; 35 and 64 are both composite.

Perfect Squares and Prime Testing

A prime candidate that is a perfect square greater than 1 is automatically composite.

For example:

169 = 13²

Therefore:

169 is composite

Its square root:

13

is a nontrivial divisor.

This also illustrates why trial division must include the square-root boundary.

Perfect Cubes and Prime Testing

Likewise, every perfect cube greater than 1 in magnitude has a nontrivial factor.

For example:

343 = 7³

so:

343 is composite

The only positive perfect cube that is prime would have to avoid a smaller factor, which no n³ with n > 1 can do.

Prime Numbers and Permutations

The permutations formula contains factorial products:

nPr = n!/(n-r)!

Prime numbers can appear as factors of these counts.

For example:

7P3 = 7 × 6 × 5

= 210

Prime-factorize:

210 = 2 × 3 × 5 × 7

This prime structure can be useful for checking divisibility of combinatorial counts, though it does not determine whether a problem itself is a permutation problem.

Prime Factors in Permutations and Combinations

The formulas compared under permutations and combinations often contain large factorial ratios.

Prime-factor methods can simplify or analyze those values.

For example:

10C3 = 120

and:

120 = 2³ × 3 × 5

The number 120 is composite even though some of the numbers used to build the factorial expression may be prime.

Primality is a property of the resulting integer, independent of the counting interpretation.

Are There Infinitely Many Prime Numbers?

Yes.

A classical argument begins by assuming only finitely many primes exist:

p₁, p₂, …, pₙ

Construct:

N = p₁p₂…pₙ + 1

When N is divided by any listed prime, the remainder is:

1

Therefore none of those primes divides N.

But every integer greater than 1 is either prime or has a prime factor.

So N introduces a prime factor absent from the supposedly complete list.

That contradiction proves:

There are infinitely many prime numbers

There Is No Largest Prime

Because infinitely many primes exist, there is no final or largest prime number.

No matter how large a known prime is, larger primes exist.

However, prime gaps can become large, so primes are not evenly spaced.

Prime Density Decreases

Although there are infinitely many primes, they become less common relative to all integers as numbers grow larger.

Informally, near a large number x, the fraction of integers that are prime is roughly associated with:

1/ln(x)

This is an asymptotic statement from deeper number theory, not a direct rule for deciding whether an individual integer is prime.

For hand testing, divisibility and square-root bounds remain more practical.

Common Mistake: Calling 1 Prime

The number 1 has only one positive factor.

A prime requires exactly two.

Therefore:

1 is not prime

Common Mistake: Assuming Every Odd Number Is Prime

All primes greater than 2 are odd, but many odd numbers are composite.

Examples:

9 = 3²

15 = 3 × 5

21 = 3 × 7

25 = 5²

Oddness is necessary for primes greater than 2, but it is not sufficient.

Common Mistake: Testing Every Number Below n

To determine whether:

997

is prime, you do not need to try every possible divisor from 2 through 996.

Since:

√997 ≈ 31.6

only prime divisors up to 31 need to be tested.

This dramatically reduces the work.

Common Mistake: Stopping Before Testing √n

Suppose:

n = 169

Then:

√169 = 13

If testing stopped below 13, the factor:

13

would be missed.

The boundary must include:

all prime divisors ≤ √n

Common Mistake: Assuming 6k ± 1 Means Prime

Numbers such as:

25, 35, 49, 55

have form 6k ± 1 but are composite.

The rule only states that primes greater than 3 must lie in those residue classes.

Common Mistake: Confusing Prime Factor With Prime Number

In:

84 = 2² × 3 × 7

the prime factors are:

2, 3, 7

The number:

84

itself is not prime.

Prime factors are prime divisors of another number.

How to Check a Claimed Prime

Suppose someone claims:

137

is prime.

Estimate:

√137 ≈ 11.7

Test primes:

2, 3, 5, 7, 11

137 is odd.

Digit sum:

1 + 3 + 7 = 11

so not divisible by 3.

Not divisible by 5.

137 ÷ 7

is not an integer.

137 ÷ 11

is not an integer.

No prime ≤ √137 divides it.

Therefore:

137 is prime

Frequently Asked Questions

What is a prime number?

A prime number is a positive integer greater than 1 with exactly two positive factors: 1 and itself.

Is 1 a prime number?

No. One is neither prime nor composite.

Is 2 a prime number?

Yes. It is also the only even prime.

Is 0 a prime number?

No.

Are all odd numbers prime?

No. For example, 9, 15, and 21 are odd composite numbers.

How do you test whether a number is prime?

Test prime divisors up to the square root of the number. If none divides exactly, the number is prime.

Why do you only test up to the square root?

If a composite number had both factors greater than its square root, their product would exceed the number itself.

Is 97 prime?

Yes. No prime number up to √97 divides it.

Is 121 prime?

No.

121 = 11²

Is 143 prime?

No.

143 = 11 × 13

Is 149 prime?

Yes. The primes up to √149 ≈ 12.2 are 2, 3, 5, 7, and 11, and none divides 149.

Are there infinitely many prime numbers?

Yes.

What are the prime numbers below 20?

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

What form do primes greater than 3 have?

Every prime greater than 3 has the form:

6k ± 1

but not every number of that form is prime.

Final Example

Determine whether:

317

is prime.

Estimate the square root:

√317 ≈ 17.8

Therefore test prime divisors:

2, 3, 5, 7, 11, 13, 17

317 is odd, so not divisible by 2.

Digit sum:

3 + 1 + 7 = 11

so not divisible by 3.

It does not end in 0 or 5.

Test 7:

317 ÷ 7

is not an integer.

Test 11:

11 × 28 = 308

11 × 29 = 319

so no.

Test 13:

13 × 24 = 312

13 × 25 = 325

so no.

Test 17:

17 × 18 = 306

17 × 19 = 323

so no.

No prime divisor at or below:

√317

divides 317.

Therefore:

317 is prime

The essential testing rule is:

To test n > 1 for primality, check prime divisors only up to √n.

For ranges, repeated divisibility elimination can identify many primes efficiently, while prime factorization explains why every composite number must eventually be removed.