##### Prime and Composite numbers

Prime numbers are numbers that have exactly two factors: one and the number itself.

Composite numbers are numbers that have more than two factors.

## Finding prime numbers

Over 2000 years ago, a Greek mathematician called “Eratosthenes” made a simple tool for sorting out prime numbers. This tool is called the “Sieve of Eratosthenes” and the figure below shows how it works for prime numbers up to 100.

#### Some facts about prime numbers

- 0 and 1 are not prime numbers neither composite numbers.
- 2 is the only even prime number.
- Expect the 5, no other prime number ends in a 5.
- No prime number ends in zero.

#### Prime numbers up to 1000

Numbers |
Number of prime numbers | List of prime numbers |

1–100 |
25 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-200 |
21 numbers | 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199 |

201-300 | 16 numbers |
211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293 |

301-400 |
16 numbers | 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397 |

401-500 | 17 numbers |
401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499 |

501-600 |
14 numbers | 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599 |

601-700 | 16 numbers |
601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691 |

701-800 | 14 numbers |
701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797 |

801-900 |
15 numbers | 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887 |

901-1000 | 14 numbers |
907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997 |

Total number of prime numbers (1 to 1000) = 168 |

#### Prime numbers up to 1000

Numbers |
Number of prime numbers | List of prime numbers |

1–100 |
25 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-200 |
21 numbers | 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199 |

201-300 | 16 numbers |
211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293 |

301-400 |
16 numbers | 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397 |

401-500 | 17 numbers |
401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499 |

501-600 |
14 numbers | 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599 |

601-700 | 16 numbers |
601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691 |

701-800 | 14 numbers |
701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797 |

801-900 |
15 numbers | 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887 |

901-1000 | 14 numbers |
907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997 |

Total number of prime numbers (1 to 1000) = 168 |

## Prime factors

Prime factors are the factors of a number that are also prime numbers.

Every composite all number can be broken down and written as the product of its prime factors.

You can do this using tree diagrams or using division. Both methods are shown in the example below:

#### Method 1: Tree diagram

#### Method 2: Division

Worked example 1: Group the numbers into prime and composite: 4, 7, 11, 19, 20, 47, 89, 90, 97, 100, 121, 139, 141, 155, 160.

Solution: Recall the fact that prime numbers have only two factors, one and the number itself, while composite numbers have more than two factors.

While keeping this in mind we see that:

P = 7, 11, 19, 47, 89, 97, 139 are the only numbers from the group that have the number one and the number itself as a factor.

C = 4, 20, 90, 100, 121, 141, 155, 160 they have more than two factors (Example: the factors of 20 are 1, 2, 4, 5, 10, 20) while the prime factorization is 20 = 2 x 2 x 5.

## Using prime factors to find HCF and LCM

When you are working with larger numbers you can determine the HCF or LCM by expressing each number as the product of its prime factors.

Worked example 2: Find HCF of 48 and 108.

Solution: First express each number as a product of prime factors. Use tree diagrams or division to do this.

Underline the factors common to both numbers.

Multiply these out to find the HCF.

48 = 2 x 2 x 2 x 3

108 = 2 x 2 x 3 x 3 x 3

2 x 2 x 3 = 12

HCF = 12

Worked example 3: Find the LCM of 60 and 72

Solution: First express each number as a product of prime factors. Use tree diagrams or division to do this.

Underline the largest set of multiples of each factor. List these and multiply them out to find the LCM.

60 = 2 x 2 x 3 x 5

72 = 2 x 2 x 2 x 3 x 3

2 x 2 x 2 x 3 x 3 x 5 = 360

LCM = 360