Skip to content
Tutorials Center
My learning

Topics

Lesson 3 of 38 ยท Getting Started

Factors, Multiples and Primes

Learn what factors, multiples, prime and composite numbers are, how to test divisibility, and how to write prime factorizations, with runnable code.

Numbers can be built from smaller numbers by multiplication. The pieces you multiply are factors, and the results you get by repeatedly multiplying are multiples. Prime numbers are the basic building blocks of all whole numbers greater than 1. These ideas are the key to simplifying fractions and, later, to factoring in algebra.

Factors

A factor of a whole number divides it exactly, with no remainder. Since 12 รท 3 = 4 exactly, 3 is a factor of 12. So is 4, because 12 รท 4 = 3. Factors come in pairs whose product is the number:

12 = 1 ร— 12 = 2 ร— 6 = 3 ร— 4

So the factors of 12 are 1, 2, 3, 4, 6, 12. Every number has 1 and itself as factors.

To list factors, test whole numbers 1, 2, 3, ... and stop when you reach a number whose partner is already found. The program does this for you.

Python List the factors of a number

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The % operator gives the remainder, so n % d == 0 means "d divides n exactly".

Multiples

A multiple of a number is what you get by multiplying it by 1, 2, 3, .... The multiples of 4 are 4, 8, 12, 16, 20, .... There are infinitely many, while a number has only finitely many factors. Notice the link: 3 is a factor of 12, and 12 is a multiple of 3.

Divisibility rules

These shortcuts tell you whether a number is divisible by another without long division.

Divisor Rule Example
2 Last digit is even (0, 2, 4, 6, 8) 3,846
3 Sum of the digits is divisible by 3 1,254: 1+2+5+4 = 12
4 Last two digits form a number divisible by 4 7,316: 16
5 Last digit is 0 or 5 8,745
6 Divisible by both 2 and 3 5,424
9 Sum of the digits is divisible by 9 4,293: 4+2+9+3 = 18
10 Last digit is 0 560

Prime and composite numbers

A prime number has exactly two factors: 1 and itself. The first primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. A composite number has more than two factors, like 12 or 15. The number 1 is neither: it has only one factor. The number 2 is the only even prime.

To test whether n is prime, you only need to check divisors up to the square root of n. If n has a factor larger than its square root, its partner factor is smaller, so you would have found it already.

Python Find the primes up to 50

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Prime factorization

Every whole number greater than 1 can be written as a product of primes, and (apart from order) in only one way. This is called its prime factorization.

To find it, use a factor tree: split the number into any two factors, then split each composite factor again until only primes remain.

flowchart TD
    A["60"] --> B["6"]
    A --> C["10"]
    B --> D["2"]
    B --> E["3"]
    C --> F["2"]
    C --> G["5"]

The leaves of the tree are the primes: 60 = 2 ร— 2 ร— 3 ร— 5.

We write repeated factors with an exponent: 60 = 2ยฒ ร— 3 ร— 5. (Exponents get their own lesson later; 2ยฒ just means 2 ร— 2.)

Try another route: 60 = 4 ร— 15 = (2 ร— 2) ร— (3 ร— 5). The same primes appear. That is the uniqueness at work.

The program below divides out the smallest possible prime again and again.

Python Prime factorization by repeated division

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For 97 the output is just 97: a prime is its own factorization.

// is whole-number division, so n //= d replaces n with the quotient. Here the division is always exact.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which list is exactly the factors of 18?

    The pairs are 1ร—18, 2ร—9 and 3ร—6. The number 4 does not divide 18 exactly.
  2. 2. Which number is prime?

    51 = 3 ร— 17 and 57 = 3 ร— 19, and 1 has only one factor. 53 has no divisor between 2 and 7, so it is prime.
  3. 3. Is 2,574 divisible by 3?

    The digit sum is 18, which is divisible by 3, so 2,574 is divisible by 3. (It is also divisible by 9, since 18 is.)
  4. 4. What is the prime factorization of 72?

    72 = 8 ร— 9 = (2ร—2ร—2) ร— (3ร—3). The other options contain composite numbers (18, 8, 9).

Summary

  • A factor divides a number exactly; a multiple is a number times 1, 2, 3, and so on.
  • Divisibility rules (for 2, 3, 4, 5, 6, 9, 10) save time.
  • A prime has exactly two factors; 1 is neither prime nor composite.
  • Every whole number above 1 has one prime factorization, found with a factor tree or by repeated division.

Next: Greatest Common Factor and Least Common Multiple