# Pyhton data's structural size and loop efficiency

1. May 21, 2012

### 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 ?

2. May 22, 2012

### gsal

I lost you at "composite".

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

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

3. May 22, 2012

### AlephZero

4. May 22, 2012

### Kartik.

5. May 22, 2012

### Kartik.

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)

6. May 22, 2012

### 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.