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

Pyhton data's structural size and loop efficiency

  1. May 21, 2012 #1
    While programming to find the largest prime factor for a composite number i came across a problem that if the number taken as input exceeds a certain limit, the loop time turns out to be a very long one and some times even resembling the time taken by an infinite loop.The method used for finding the prime factors is a standard one in which we loop through natural number until the input equals the loop counter; finding its factors and then checking for it to be prime or not ;through another function by a similar method using a counter variable.? Alternatives for drastic time reduction ?
  2. jcsd
  3. May 22, 2012 #2
    I lost you at "composite".

    time reduction of what? you gonna show us some code?

    how about wrapping some 'C' or 'Fortran' code?
  4. May 22, 2012 #3


    User Avatar
    Science Advisor
    Homework Helper

  5. May 22, 2012 #4
  6. May 22, 2012 #5
    I wrote about the time it takes to loop through natural number during program execution and wanted any time-efficient method for factorization.(They have wiki pages for that too :P)
  7. May 22, 2012 #6
    I guess the simplest algorithm would be something like this:

    (1) find an efficient way to generate all prime numbers up to the square root of the input. Something like Sieve. Or use a pre-calculated table if you know what the largest input number is.

    (2) start checking from the smallest prime=2 up.

    (3) as soon as you find a prime factor, divide the input number by this factor. Do this several times if the factor occurs in a higher power than 1. Dividing will make the test number smaller and subsequent tests faster (assuming your input is larger than standard 32-bit integers).

    (4) repeat with the next largest prime, up to the largest prime smaller than the square root.

    (5) if you don't find a prime factor smaller than the square root, then the input number is a prime.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook