Dr. Math FAQ || Classic Problems || Formulas || Search Dr. Math || Dr. Math Home

## What is a prime number? How can you find prime numbers? What's the 'Sieve of Eratosthenes'? How can you decide if a number is prime? What's the largest known prime?
A prime number is a positive integer that has exactly two positive
integer factors, 1 and itself. For example, if we list the factors of
28, we have 1, 2, 4, 7, 14, and 28. That's six factors. If we list
the factors of 29, we only have 1 and 29. That's two factors. So we
say that 29 is a prime number, but 28 isn't. Another way of saying this is that a prime number is a positive integer that is not the product of two smaller positive integers.
Note that the definition of a prime number doesn't allow 1 to be a
prime number: 1 only has one factor, namely 1. Prime numbers have
Here are the first few prime numbers:
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, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, etc. ## The Sieve of EratosthenesEratosthenes (275-194 B.C., Greece) devised a 'sieve' to discover prime numbers. A sieve is like a strainer that you use to drain spaghetti when it is done cooking. The water drains out, leaving your spaghetti behind. Eratosthenes's sieve drains out composite numbers and leaves prime numbers behind.To use the sieve of Eratosthenes to find the prime numbers up to 100, make a chart of the first one hundred positive integers (1-100): 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 - Cross out 1, because it is not prime.
- Circle 2, because it is the smallest positive even prime. Now cross out every multiple of 2; in other words, cross out every second number.
- Circle 3, the next prime. Then cross out all of the multiples of 3; in other words, every third number. Some, like 6, may have already been crossed out because they are multiples of 2.
- Circle the next open number, 5. Now cross out all of the multiples of 5, or every 5th number.
There are various primality tests, from very simple to very complex, which allow you to determine if a given number is prime. You can read more about them at Primality Testing in our Selected Answers. There is no largest prime number, but the effort to find ever-larger primes is ongoing and you can read about The Largest Known Primes on the Web.
## From the Dr. Math archives:-
See Middle School Prime Numbers or search the Dr. Math archives using the words "prime number" (that exact phrase; just the words, not the quotes) to find questions and answers about prime numbers at all levels. Here are some good places to start:
Finding Prime Numbers ## On the Web:-
Finding Primes and Proving Primality
The First 10,000 Primes The Great Internet Mersenne Prime Search How Many Primes Are There? The Largest Known Primes Mersenne Prime - Susan Stepney Mersenne Primes - Jon Vinopal Mersenne Primes: History, Theorems and Lists Prime Number (Eric Weisstein's World of Mathematics) Prime Numbers and Factors The Prime Pages - Chris Caldwell 73939133 - Prime Numbers - Amazing Number Facts Prime Theorem of the Century Students' Mersenne Prime Page Why do people find these primes? - Chris Caldwell |

[**Privacy Policy**]
[**Terms of Use**]

Math Forum Home ||
Math Library ||
Quick Reference ||
Math Forum Search

© 1994- The Math Forum at NCTM. All rights reserved.

http://mathforum.org/