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

Thanks

BIOS

Printable View

- Dec 19th 2010, 02:15 PMBIOSQuickest 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 - Dec 19th 2010, 02:18 PMdwsmith
Example

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

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

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

If $\displaystyle 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. - Dec 19th 2010, 02:19 PMPlato
- Dec 19th 2010, 02:23 PMpickslides
Well if it ends in 0 or 5 divide 5, if endig in any other even number divide 2.

- Dec 19th 2010, 02:36 PMBIOS
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

Hey no just mean by pen and paper or mentally :) - Dec 19th 2010, 02:40 PMPlato
*cellulose-graphite*= paper & pencil. - Dec 19th 2010, 02:43 PMBIOS
Ooops my mistake dude. I thought CAS was some sort of software :P What is a CAS then?

- Dec 19th 2010, 02:45 PMdwsmith
Plato uses CAS which is a computerized algebra system(software). The question Plato asked was if you were doing it by hand.

- Dec 19th 2010, 02:48 PMBIOS
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!

- Dec 19th 2010, 02:50 PMdwsmith
Start however you like top to bottom or in the reverse will achieve the same results.

- Dec 19th 2010, 02:53 PMBIOS
Thanks DW. Will try internalise that method a bit better so!

P.S Pickslide that leaves out 3 :P - Dec 19th 2010, 02:59 PMPlato
There are so many resources available. Doing thing by hand is a waste of time.

Look at this site. - Dec 19th 2010, 03:04 PMBIOS
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.

- Dec 19th 2010, 03:09 PMPlato