Prime Numbers and the Sieve of Eratosthenes

Prime numbers are positive integers greater than 1 that have exactly two positive divisors: 1 and themselves. In brief: 13 is prime because only 1 and 13 divide it exactly; 15 is composite because 3 × 5 = 15. The Sieve of Eratosthenes finds primes by removing multiples from a list.

Primes provide the building blocks for factorization, but listing them efficiently requires more than guessing from a number’s appearance. This guide explains the definition, the square-root limit for testing and a complete sieve through 100. It also separates a procedure for finding many primes from a test for one particular number.

What are prime numbers and composite numbers?

A prime has no positive divisors other than 1 and itself. The number 7 is prime because no integer from 2 through 6 divides it exactly. A composite number is a positive integer greater than 1 that is not prime, so it has a factorization into two smaller positive integers greater than 1.

The number 1 is neither prime nor composite. It has only one positive divisor, which does not meet the prime definition. Zero also lies outside these two categories. The distinction is about positive integers greater than 1, rather than every possible numerical value.

Two is the only even prime. Every larger even integer has 2 as a divisor distinct from 1 and itself, so it is composite. All other primes are odd, but not all odd numbers are prime: 9, 15 and 21 are simple counterexamples. Being odd is a necessary condition for primes above 2, not a sufficient test.

How do you check whether one number is prime?

To test a positive integer greater than 1, look for an exact divisor other than 1 and itself. It is enough to test possible factors up to the square root. If n = a × b and both factors exceeded √n, their product would exceed n, so every composite number must have a smaller factor within that limit.

You can narrow the search to prime candidates, because any composite divisor has a prime factor that also divides the number. To test 97, check 2, 3, 5 and 7: these are all the primes at most √97, which lies between 9 and 10. None divides 97, so it is prime.

To test 91, the checks for 2, 3 and 5 fail, but 7 succeeds because 91 = 7 × 13. The number is therefore composite even though it is odd and does not end in 5. A single nontrivial divisor proves compositeness; proving primality requires completing every necessary test.

What is the Sieve of Eratosthenes?

The Sieve of Eratosthenes starts with the integers from 2 to a chosen upper bound. It repeatedly selects the smallest remaining unprocessed number and removes its larger multiples. After the required stages, every number still unmarked is prime, because all composites have been eliminated by a prime factor.

Do not remove the selected prime itself. At the stage for 2, cross out 4, 6, 8 and so on, leaving 2 in the list. At the stage for 3, remove 9, 12, 15 and later multiples as needed. Some values were already removed, and marking them again changes nothing.

The sieve is especially useful when you want all primes in an interval beginning at 2. Trial division is often simpler when you need to inspect only one small number. Both methods rely on prime factors and the square-root bound, but their organization differs: the sieve marks multiples, whereas a single-number test checks potential divisors.

How do you use the sieve to find primes up to 100?

Write every integer from 2 through 100 and begin with 2. Cross out its multiples from 4 onward, then select 3 and cross out its multiples from 9 onward. The next unmarked value is 5; mark its multiples from 25 onward. Then process 7 from 49 onward.

You may start each prime’s marking at its square because smaller multiples already have a smaller prime factor. For 7, the multiples 14, 21, 28, 35 and 42 were removed during earlier stages. Beginning at 49 avoids redundant work without overlooking a composite.

After processing 7, the next unmarked prime is 11, and 11 squared is 121, greater than 100. You can stop crossing out multiples and read all the unmarked values as primes. The remaining numbers include 11 itself and later primes; they do not need separate marking stages within this range.

1. List 2 through 100; exclude 1 from the outset.
2. Keep 2 and mark its multiples starting at 4.
3. Keep 3, 5 and 7, marking from 9, 25 and 49 respectively.
4. Stop when the next prime squared exceeds 100.
5. Collect every unmarked number in increasing order.

Complete list of prime numbers from 1 to 100

The table contains every prime in the stated interval, organized into consecutive bands for readability. The bands do not mean that every integer in each band is prime; the right column gives the complete prime list for that band. There are 25 primes from 1 through 100.

Notice that the final digit alone cannot identify a prime. Above 5, a prime must end in 1, 3, 7 or 9, but composite numbers can have those endings too. For example, 77 ends in 7 but equals 7 × 11, and 99 ends in 9 but equals 9 × 11.

Spacing between primes varies. The values 11 and 13 differ by 2, while 89 and 97 differ by 8. The sieve does not assume a repeating gap pattern; it relies on exact factor relationships. A list should therefore be checked by a method, rather than extended from an apparent visual pattern.

Why does the sieve work and why are there infinitely many primes?

Every composite number has a prime factor no greater than its square root. Therefore every composite at most N has a prime factor no greater than √N. Processing those primes removes every composite in the range, while a prime cannot be removed as a larger multiple of a smaller prime.

There are infinitely many primes. To understand the classic argument, suppose you had a complete finite list and multiplied all its primes together, then added 1. Dividing this new number by any listed prime would leave remainder 1, so none of the listed primes could divide it.

The new number is either prime or has a prime factor absent from the supposedly complete list. Either possibility contradicts completeness. The constructed number does not have to be prime itself: the argument only requires a new prime factor. Confusing those claims is a common mistake when explaining why the prime sequence never ends.

Where did the sieve come from, and how are primes used today?

The sieve is named for the ancient Greek scholar Eratosthenes and belongs to the long history of studying whole-number relationships. Its familiar classroom form remains useful because the logic is easy to display: keep primes and remove the quantities built from them. A computer can use the same marking idea over a much larger range.

Primes support unique prime factorization, efficient calculation of common factors and the study of modular arithmetic. They also appear in some cryptographic systems, although listing a few small primes is not a complete description of how those systems work. For beginner arithmetic, their most direct role is organizing factors and divisibility.

Avoid including 1, crossing out the selected prime or stopping before every required small prime has been processed. Another error is declaring every unmarked number prime halfway through the sieve. For a range ending at 100, the stages for 2 and 3 alone leave 25 and 49 unmarked, even though both are composite.

Frequently asked questions

Why is 1 not prime?

One is not prime because it has only one positive divisor. A prime must have exactly two distinct positive divisors.

Is 2 a prime number?

Two is prime because its positive divisors are exactly 1 and 2. It is the only even prime.

Why does marking begin at the prime’s square?

Smaller multiples already have a smaller prime factor and were removed earlier. Starting at the square reduces repeated work while preserving every necessary elimination.

Do you cross out numbers after the square-root stopping point?

No new marking stage is needed once the next selected prime squared exceeds the upper bound. Every composite in the range has already been marked.

Is the product of known primes plus 1 always prime?

The product plus 1 is not always prime. It is not divisible by any of the primes in that product, so it must be prime or have a different prime factor.