# Quickest way of working out prime factoring of large numbers

• December 19th 2010, 02:15 PM
BIOS
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
• December 19th 2010, 02:18 PM
dwsmith
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.
• December 19th 2010, 02:19 PM
Plato
Quote:

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.
• December 19th 2010, 02:23 PM
pickslides
Well if it ends in 0 or 5 divide 5, if endig in any other even number divide 2.
• December 19th 2010, 02:36 PM
BIOS
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

Quote:

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 :)
• December 19th 2010, 02:40 PM
Plato
cellulose-graphite = paper & pencil.
• December 19th 2010, 02:43 PM
BIOS
Ooops my mistake dude. I thought CAS was some sort of software :P What is a CAS then?
• December 19th 2010, 02:45 PM
dwsmith
Plato uses CAS which is a computerized algebra system(software). The question Plato asked was if you were doing it by hand.
• December 19th 2010, 02:48 PM
BIOS
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!
• December 19th 2010, 02:50 PM
dwsmith
Start however you like top to bottom or in the reverse will achieve the same results.
• December 19th 2010, 02:53 PM
BIOS
Thanks DW. Will try internalise that method a bit better so!

P.S Pickslide that leaves out 3 :P
• December 19th 2010, 02:59 PM
Plato
There are so many resources available. Doing thing by hand is a waste of time.
Look at this site.
• December 19th 2010, 03:04 PM
BIOS
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.
• December 19th 2010, 03:09 PM
Plato
Quote:

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.