# Thread: Quickest way of working out prime factoring of large numbers

1. ## Quickest way of working out prime factoring of large numbers

I was wondering if anyone has a particular method of working out the prime factoring of say numbers greater than 3 digits.

Thanks

BIOS

2. Example

$\displaystyle \left\lfloor\sqrt{627}\right\rfloor = 25$

Now, check to see if all primes $\leq 25$ divide 627.

If 0,2,4,6,8| the last digit, then 2|627

If $6+2+7\equiv 0 \ \mbox{(mod 3)}$, then 3|627.

For 5, the last digit needs to be 0 or 5.

For 7, double the last digit 7*2=14 and subtract it from the remaining digits 62-14=48, and if 7|48, then 7|627.

For 11, subtract the last digit from the remaining digits 62-7=55, and if 11|55 which it does, then 11|627.

For 13, add 4 times the last digit 62+28=90, and if 13|90, then 13|627.

I only know rules for up to 13.

3. Originally Posted by BIOS
I was wondering if anyone has a particular method of working out the prime factoring of say numbers greater than 3 digits.
Do you mean using the cellulose-graphite method?
I use a CAS. Quick and easy.

4. Well if it ends in 0 or 5 divide 5, if endig in any other even number divide 2.

5. Thanks for the replies.

Dwsmith that's what i suspected. Just learn the divisibility rules for all primes up to say 13 is probably the most practical way. Was just wondering if there was an alternate method i should be aware of :P

Originally Posted by Plato
Do you mean using the cellulose-graphite method?
I use a CAS. Quick and easy.
Hey no just mean by pen and paper or mentally

6. cellulose-graphite = paper & pencil.

7. Ooops my mistake dude. I thought CAS was some sort of software :P What is a CAS then?

8. Plato uses CAS which is a computerized algebra system(software). The question Plato asked was if you were doing it by hand.

9. Thanks for the clarification! I thought as much. So to sum up the best way is to just start at the smallest prime and move upwards if they don't pass the divisibility rule. I don't know if it's just me but i always feel like i'm cheating when i use those tricks/rules!

10. Start however you like top to bottom or in the reverse will achieve the same results.

11. Thanks DW. Will try internalise that method a bit better so!

P.S Pickslide that leaves out 3 :P

12. There are so many resources available. Doing thing by hand is a waste of time.
Look at this site.

13. Thanks for the link Plato. Looks like a very useful resource. I do still think it's good practice to be able to do reasonable arithmetic in your head or on paper well but yeah for larger calculations you're absolutely right.

14. Originally Posted by BIOS
I do still think it's good practice to be able to do reasonable arithmetic in your head or on paper well but yeah for larger calculations you're absolutely right.
I too agree with that. If we want to factor something like 172.
But go back to that site and ask it to factor (55!).
You can see all primes less that 55.