# Factoring a Number

To factor a number, it is important to know the divisibility rules below reminded.

## Divisibility rules

These simple rules are very useful for factoring a number.

### Divisibility by 2

A number is divisible by 2 if its last digit is even.Example: 65

__4__is divisible by 2 because 4 is even.

### Divisibility by 3

A number is divisible by 3 if the sum of its digits is divisible by 3.Example: 654 is divisible by 3 because 6 + 5 + 4 = 15 which is divisible by 3.

### Divisibility by 4

A number is divisible by 4 if the number formed by its last two digits is divisible by 4.Example: 1235

__24__is divisible by 4 because 24 is divisible by 4.

### Divisibility by 5

A number is divisible by 5 if the last digit is 0 or 5.Example: 654352

__5__

### Divisibility by 6

A number is divisible by 6 if it is divisible by 2 and 3 (see the 2 and 3 rules above).862

__2__is divisible by 6 because it's divisible by 2 (the last digit is even) and it's divisible by 3 (the sum of its numbers is 8+6+2+2=18 which is divisible by 3).

### Divisibility by 9

A number is divisible by 9 if the sum of its digits is divisible by 9.Example: 165411 is divisible by 9 because 1+6+5+4+1+1=18 which is divisible by 9.

### Divisibility by 10

A number is divisible by 10 if the last digit is 0.Example: 435

__0__is divisible by 10.

## How to factor a number ?

Divide the number by successive prime numbers 2, 3, 5, 7, etc. Foreach prime number, repeat the operation until you get a remainder. All the factors are found when you get at last a prime number.

Example: how to factor 1092 ?

- Repeat the division by 2 until you get a remainder

`1092 = 2 * 546`

`546 = 2 * 273`

`273 = 2 * 136 + 1`

End of division by 2 because of the remainder. Write the result,

`1092 = 2 * 2 * 273`

- Repeat the division by 3 until you get a remainder

`273 = 3 * 91`

`91 = 3 * 30 + 1`

End of division by 3 because of the remainder. Write the result,

`1092 = 2 * 2 * 3 * 91`

- Repeat the division by 5 until you get a remainder

`91 = 5 * 18 + 1`

End of division by 5 because of the remainder.

- Repeat the division by 7 until you get a remainder

`91 = 13 * 7`

End of factorization because 7 is a prime number. We write the final result,

`1092 = 2^2 * 3 * 13 * 7`

Note that,

- In practice, you may combine this method with the divisibility rules to quickly find the divisors of a number without trying the division by all the possibilities. Example, to factorize 1343, knowing our divisibility rules, it's no worth trying to divide by 2, 3 and 5.

- A non-prime number always has a divisor lower than its square root. As a result, the search for divisors can be limited to prime numbers between 2 and `E (sqrt (N)) `(integer part of the root of N).

## List of prime numbers

- **Prime numbers from 1 to 10**

2, 3, 5, 7

- **The prime numbers from 11 to 100**

11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

- **Prime numbers from 101 to 1000**

101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997

## Programming

Here is how we program the factorization of a number into prime factors.### Python

```
def factorize (n):
i = 2
factors = []
while i * i <= n:
if n% i:
i += 1
else:
n//= i
factors.append (i)
if n > 1:
factors.append (n)
return factors
```

## See also

Find all divisors of a number

Test if a number is prime or not

Search prime numbers