Factoring a Number
To factor a polynomial, eg. : x2 - 1, use : Factor a polynomial
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: 654 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: 123524 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: 6543525
Divisibility by 6
A number is divisible by 6 if it is divisible by 2 and 3 (see the 2 and 3 rules above).8622 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: 4350 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