Pyhton data's structural size and loop efficiency

[Kartik.]

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 ?

 

[gsal]

I lost you at "composite".

time reduction of what? you going to show us some code?

how about wrapping some 'C' or 'Fortran' code?

 

[AlephZero]

Alternatives for drastic time reduction ?

http://en.wikipedia.org/wiki/Integer_factorization

 

[Kartik.]

http://en.wikipedia.org/wiki/Integer_factorization

Thanks

 

[Kartik.]

I lost you at "composite".

time reduction of what? you going to show us some code?

how about wrapping some 'C' or 'Fortran' code?

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)

 

[M Quack]

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.