Prime and Composite Numbers

Natural numbers are the set of numbers we use when we count.

{1, 2, 3, 4, 5, 6, 7, …}

A prime number is a natural number that can be divided, without leaving

any remainder, by only itself and one.

A prime number has only two factors, itself and one.

For example, 5 can be divided, without a remainder, only by 5 and 1.

5 has exactly two natural number factors, 5 and 1.

5 is a prime number.

A composite number is an natural number that can be divided, without

leaving any remainder, by a natural number other than itself and one.

For example,

2 = 1 × 2 Prime

3 = 1 × 3 Prime

6 = 1 × 6 and 2 × 3 Composite

6 can be divided by 2 and by 3, so 6 is composite.

15 = 1 × 15 and 3 × 5  Composite

15 can be divided by 3 and by 5, so 15 is composite.

Interesting fact 1:

There is exactly one even prime number. It is also the smallest prime

number. Do you know what it is?

Interesting fact 2:

Prime numbers are interesting to scientists, especially the large ones.

Large prime numbers are used as keys in the codes that are used to send

secret messages. Since these are not easy to find, the codes are difficult to

break.

When you try to decide if a larger number is prime, you really only need to

find out if it is divisible by prime numbers that are less than it is.

Prime Factorization

Every number has one prime factorization.

Example: Find the prime factorization of 159.

159 is not divisible by 2 or any other even number.

159 is divisible by 3: 159 = 3 × 53

53 is a prime number.

3 is a prime number.

The prime factorization of 159 is 159 = 3 × 53.

Factor Trees may extend further:

The Sieve of Eratosthenes

Over 2000 years ago, Eratosthenes, a Greek who studied mathematics and

was the third librarian of the library at Alexandria, was also interested in

prime numbers. He lived from 276 BC until 194 BC. He is credited with the

development of what we now call the “Sieve of Eratosthenes”.

He arranged numbers in ten columns. One (1) is not a prime number. Its

only factor is itself. Then, since 2 is the first prime number, he crossed off

every second number following 2, like this:

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

3 is the next prime number. So Erastosthenes crossed out every third

number.

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

The next number that has not been crossed out is the next prime number.

This time it is 5. Erastosthenes circled the five and crossed out every fifth

number.

This process can be continued as long as you have time, patience, and a

list of counting numbers. All of the numbers that are crossed out are

composite numbers.

On the next page is a list of numbers from 1 to 200. Use the sieve of

Erastothenes to find all of the prime numbers less than 200.

X X

X

X

X

X X

X

X X

X X X X XX

X

X X X

X X X X

X X

X

X

X

X X

X

X X

X X X X XX

X

X X X

X X X X

The Sieve of Eratosthenes

Cross out 1. It is not a prime number.

Circle 2.

Cross out all of the multiples of 2: 4, 6, 8, 10, 12, 14, 16, …

Circle the next number that has not been crossed out: 3.

Cross out the multiples of 3.

Continue until all of the numbers that are multiples of the primes have been

crossed out. The numbers that are left are prime numbers.