Results 1 to 14 of 14

Math Help - Quickest way of working out prime factoring of large numbers

  1. #1
    Junior Member
    Joined
    Sep 2010
    Posts
    68

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1
    Quote Originally Posted by BIOS View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Master Of Puppets
    pickslides's Avatar
    Joined
    Sep 2008
    From
    Melbourne
    Posts
    5,236
    Thanks
    28
    Well if it ends in 0 or 5 divide 5, if endig in any other even number divide 2.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Sep 2010
    Posts
    68
    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 View Post
    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
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1
    cellulose-graphite = paper & pencil.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Sep 2010
    Posts
    68
    Ooops my mistake dude. I thought CAS was some sort of software :P What is a CAS then?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    Plato uses CAS which is a computerized algebra system(software). The question Plato asked was if you were doing it by hand.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Sep 2010
    Posts
    68
    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!
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    Start however you like top to bottom or in the reverse will achieve the same results.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Junior Member
    Joined
    Sep 2010
    Posts
    68
    Thanks DW. Will try internalise that method a bit better so!

    P.S Pickslide that leaves out 3 :P
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1
    There are so many resources available. Doing thing by hand is a waste of time.
    Look at this site.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Junior Member
    Joined
    Sep 2010
    Posts
    68
    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.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1
    Quote Originally Posted by BIOS View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Prime factoring a large number.
    Posted in the Algebra Forum
    Replies: 5
    Last Post: September 10th 2011, 04:10 AM
  2. Prove a large number is prime
    Posted in the Number Theory Forum
    Replies: 9
    Last Post: February 1st 2011, 10:17 PM
  3. Comparing large prime powers.
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: November 9th 2010, 07:08 AM
  4. Generating Large Prime Numbers
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: July 26th 2009, 02:08 PM
  5. factoring a large polynomial
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 29th 2008, 06:38 PM

Search Tags


/mathhelpforum @mathhelpforum