Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Finding all divisors of a number

  1. Feb 9, 2009 #1

    ShayanJ

    User Avatar
    Gold Member

    Good time people
    Is there any way other than dividing the number from 2 to its half to find all of its divisors?
    Anyway may help so feel free telling your ideas
    thanks
     
  2. jcsd
  3. Feb 9, 2009 #2
    First of all you don't have to divide up to the number's half, only up to it square root. Second, you only have to divide by prime numbers.
     
  4. Feb 9, 2009 #3

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    It's easiest to first find all the prime factors of a number, and then determine the divisors from that list. Finding the prime factors requires only trial dividing up to the square root of the number -- and then only by the primes, if you like.

    Methods like Pollard's rho algorithm, elliptic curve factoring, and the number field sieves can be used to factor large numbers (say, > 10^9) much more quickly.

    Practically, if you don't recognize these terms, I recommend a tool like
    http://www.alpertron.com.ar/ECM.HTM
     
  5. Feb 11, 2009 #4

    ShayanJ

    User Avatar
    Gold Member

    Hello
    Did you noticed 71,a prime factor of 284?
    it is greater than 16.85 that is the square root of 284.
     
  6. Feb 11, 2009 #5

    ShayanJ

    User Avatar
    Gold Member

    And one more thing...
    Could you explain the methods you named?
    the page you gave the link of,doesn't include a explanation about the method itself.
    I searched it in the internet but i found no easy explanation.
    thanks
     
  7. Feb 11, 2009 #6
    Hi Shyan,

    I had visited a site called eTutorWorld its online tuition site.
     
  8. Feb 11, 2009 #7

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Yes, but 284=71*4. So by finding 4, you've found 71 as a factor also. If a> sqrt(n), and ab = n, then b<sqrt(n) necessarily.
     
  9. Feb 11, 2009 #8

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Yes, but I think Shyan was referring to Skeptic2's advice to only go up to and only use prime numbers. 2 divides into 284 142 times but you don't immediately see the "71". Of course the intelligent thing to do once you have 284= 142 would be to ignore the 284 and start factoring 142 so that you immediately get 2*71 but it is not clear that was what Skeptic2 meant.
     
  10. Feb 11, 2009 #9
    Agreed.
     
  11. Feb 11, 2009 #10

    ShayanJ

    User Avatar
    Gold Member

    Please!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook