Are there any tricks or shortcuts to prime factorization?

Question

I am having a hard time finding the prime factorization of different numbers. Here is an example: $924=2^2 * 3 *7 *11$

• Are there any shortcuts or tricks that lead to the prime factorization?
• What methods can I use when trying to find prime factorization?

I tried to find the factorization with the factorization tree

             924
            /   \
           3    308
               /   \
              2    254
                  /   \
                 2    127 <-- stuck here

Thanks in advance

Answer 1

Broadly speaking, factorisation is a hard problem (and it is specifically "hard" in a way that enables certain forms of cryptography). However, if you're factoring relatively small numbers, here are some things that can help:

1. As I think you already know, if a decimal number ends in 0, 2, 4, 6 or 8, then it is divisible by 2.
2. Similarly, if it ends in 0 or 5, then it is divisible by 5.
3. If the sum of the digits is divisible by 3, then the number is divisible by 3.
4. If the sum of the odd-positioned digits, subtracted from the sum of the even-positioned digits, is divisible by 11, then the number is divisible by 11 (for example, in 132 you have 1+2-3=0 and 132=11×12).
5. If a number has no factors, other than 1, that are less than or equal to its square root, then the number is prime.

If you want some more complicated tricks, there are a few at the following links:

• http://www.murderousmaths.co.uk/books/bkmm1x11.htm
• http://www.savory.de/maths1.htm
• https://en.wikipedia.org/wiki/Divisibility_rule

Answer 2

Your above division is wrong ($\frac{308}{2}$ = 154). But either way, if it's not divisible by a number smaller than its square root, then it's a prime.

For divisibility by 11, add all the digits in even positions (tens, thousands, etc), and subtract the sum from the sum of all digits in odd positions (units, hundreds, etc). If the difference is divisible by 11, then the number is divisible by 11.

Answer 3

Here are some notes which can make prime factorization easier:

You can equally fragment the number and then find the prime factor of each fragment. 


Here's an example: 
Problem: For n = 484, find its prime factors. 
Solution: 
480 = 10 × 48
Now, we just have to find the prime factors of 10  and 48 and merge them into a single group which will be the solution to our problem (prime factors of 480). 
Prime factors of 10: 5, 2
Prime factors of 48: 2, 2, 2, 2, 3
Therefore, prime factors of 480 are 5, 2, 2, 2, 2, 2, 3.

• Prime factorization becomes a cinch when you are given a square integer and you know its square root. Just find out the prime factors of its square root and merge those factors into a group having those factors two times. 


Here's an example to demonstrate this method:
Problem: For n = 81, find its prime factors. 
Solution: 
Let s be the square root of n. 
Therefore, s = 9
So, the prime factors of 81 are [prime factors of 9] × 2 times. 
Prime factors of 9 are 3, 3. 
Therefore, prime factors of 81 are [3, 3] × 2 times = 3, 3, 3, 3

• The above method can be applied to any integer which has been raised by an exponent. Just find the prime factors of the number which was raised to that power and merge the number in a group exponent times. 
Here's an example:
Problem: For n = 27000, find its prime factors. 
Solution: 
Since we all know that 27000 is 30³ (30 is the cube root of 27000), we just need to find the prime factors of 30 and merge them into a group 3 times.
Prime factors of 30: 5, 2, 3
Therefore, prime factors of 27000 are 
[5, 2, 3] × 3 times, which is 5, 2, 3, 5, 2, 3, 5, 2, 3.