Python several billion iteration loop

Question

I'm new to programming, so please bear with me.

I wrote this code to find the largest prime factor of a number, but when I input a number of a billion or greater it doesn't solve. I've tried xrange, but I'm using Python 3.4. Can anyone point me in the right direction?

done = False

num = int(input("Enter a number: "))

for j in range(num,2,-1):

        if (num % j) != 0:
            continue
        for i in range(2,j):     
            if (j % i) != 0:
                continue
            break


        else: break

print(j)

I misunderstood the implications of `else: break`. That being said, I suspect that your problem is that your code just takes a long time to run. — Bill Lynch, Sep 06 '14 at 02:24
possible duplicate of [Largest prime factor of a number](http://stackoverflow.com/questions/23287/largest-prime-factor-of-a-number) — simonzack, Sep 06 '14 at 02:28
Make sure the posted code is an *accurate* representation of the problem. That is still not it. — user2864740, Sep 06 '14 at 02:29
How is it not an accurate representation of the problem? The code in it's current format(as written above) is the problem. — jdgalaway, Sep 06 '14 at 02:35
possible duplicate of [Python Finding Prime Factors](http://stackoverflow.com/questions/15347174/python-finding-prime-factors) — forivall, Sep 06 '14 at 02:41
@forivall, I'm trying to get my code to compute with numbers larger than 1 billion. The link you posted asked why one is faster than the other. — jdgalaway, Sep 06 '14 at 02:50
@jdgalaway no, it's about algorithm design. Notice what I said below about how much you're looping? Look at the math, and try to figure out how many times a line with a `%` is executed. Paste the code into here (http://pythontutor.com/visualize.html) and run it with small numbers. — forivall, Sep 06 '14 at 02:55
Ahh... ok. As mentioned ^^^, I'm new to this, and I'm trying. — jdgalaway, Sep 06 '14 at 03:05
This is going to give you `3` for any power of 2… that can't be right. — abarnert, Sep 06 '14 at 04:19
See [this question](http://stackoverflow.com/questions/110344/algorithm-to-calculate-the-number-of-divisors-of-a-given-number) for some useful ideas. Also see [integer factorization](http://en.wikipedia.org/wiki/Integer_factorization) on Wikipedia. — abarnert, Sep 06 '14 at 05:18

forivall · Answer 1 · 2014-09-06T02:30:55.173

2

It's an O(n^2) algorithm. It doesn't appear to solve because it's just taking a long time. Solution? Use numpy. Or find a non-naive algorithm, or write one yourself. The sieve of Eratosthenes is a good starting point.

edited Sep 06 '14 at 02:30

answered Sep 06 '14 at 02:25

forivall

9,504
2
33
58

I don't think numpy's designed for factoring numbers? – simonzack Sep 06 '14 at 02:27
Interesting. I'll do some research. Much appreciated... So far :) – jdgalaway Sep 06 '14 at 02:37
also, in case you didn't catch it, lookup big-o notation (that's what O(n^2) means -- that you're not only looping a billion times, but a billion squared times! – forivall Sep 06 '14 at 02:40
I didn't catch that, but I did realize that the nested loop was amplifying the issue. – jdgalaway Sep 06 '14 at 02:44
I don't think it's `O(n^2)`. It doesn't do linear work for every number up to `n`, it only does linear work for each factor of `n`, and isn't that algorithmically smaller than `n`? – abarnert Sep 06 '14 at 04:31
(Worst case `n^.5+2` and average case a whole lot better? I forget…) But obviously it's a lot slower than, e.g., using the prime factors, and computing the primes with a memoized sieve… – abarnert Sep 06 '14 at 04:37
@abarnert remember that big-o notation is simply an upper bound, although you are right in that the upper bound that I set is bigger than it needs to be. – forivall Sep 08 '14 at 17:06
@forivall: True, but you wouldn't call a linear algorithm `O(2^n)` as an explanation of why it's too slow, even though it's technically true… (Anyway, I was hoping someone would either know the worst-case and average-case complexity for doing linear work on every factor of `N`, because it seems like something I should remember, and yet I don't… Of course in prime-related algorithms you're talking about the complexity in the number of bits in N rather than N anyway, so maybe I shouldn't know this…) – abarnert Sep 08 '14 at 17:33

score 1 · Answer 2 · 2015-10-08T16:58:44.497

Since you are new to programming, here is a simple solution (but know that there are substantially more complex solutions that are more efficient). First note that you only need to check divisors up to the square root of num, since if num = a * b then one is less than the square root and one is larger. Secondly you only need to check for prime divisors.

You can generate a list of primes as follows:

import math
import itertools

def primes_generator():
    """Generator for the infinite list of primes."""
    primes = [2, 3]
    for prime in primes:
        yield prime
    for c in itertools.count(5, 2):
        bound = math.sqrt(c)
        for p in primes:
            if not (c % p):
                break
            if p > bound:
                primes.append(c)
                yield c
                break

Now to find the all the prime divisors:

def prime_factorization(number, primes=None):
    if not primes:
        primes = primes_generator()
    factorization = dict()
    for p in primes:
        count = 0
        while not (number % p):
            number = number / p
            count = count + 1
        if count:
            factorization[p] = count
        if number == 1:
            return factorization

The largest prime divisor is just the largest key in the dictionary. These functions should work fine for fairly large inputs. On my machine the following takes 0.06 seconds.

 print(max(prime_factorization(1000000001).keys()))

I know, people say, hey, you can buy flies at the store — but you can buy your fish at the store, Ed, you see what I'm saying? Sure, go to the store. Go there, describe to the man where you will be fishing, and for what, and the weather conditions, sun, no sun, whatnot, and so forth, and then you might as well have the man go ahead and sell you the goddamn _fish_. — msw, Sep 06 '14 at 05:31

Python several billion iteration loop

2 Answers2