How can this be made to do fewer calculations? It is very inefficient with large numbers

Question

num = input ()
fact = 0
while fact != num:
     fact = fact + 1
     rem = num % fact
     if rem == 0:
          print fact

Answer 1

You only need to go to the square root of the input number to get all the factors (not as far as half the number, as suggested elsewhere). For example, 24 has factors 1, 2, 3, 4, 6, 8, 12, 24. sqrt(24) is approx 4.9. Check 1 and also get 24, check 2 and also get 12, check 3 and also get 8, check 4 and also get 6. Since 5 > 4.9, no need to check it. (Yes, I know 24 isn't the best example as all whole numbers less than sqrt(24) are factors of 24.)

factors = set()
for i in xrange(math.floor(math.sqrt(x))+1):
    if x % i == 0:
        factors.add(i)
        factors.add(x/i)
print factors

There are some really complicated ways to do better for large numbers, but this should get you a decent runtime improvement. Depending on your application, caching could also save you a lot of time.

Answer 2

Use for loops, for starters. Then, let Python increment for you, and get rid of the unnecessary rem variable. This code does exactly the same as your code, except in a "Pythonic" way.

num = input()
for x in xrange(1, num):
    if (num % x) == 0:
        print fact

xrange(x, y) returns a generator for all integers from x up to, but not including y.

Answer 3

So that prints out all the factors of a number? The first obvious optimisation is that you could quit when fact*2 is greater than num. Anything greater than half of num can't be a factor. That's half the work thrown out instantly.

The second is that you'd be better searching for the prime factorisation and deriving all the possible factors from that. There are a bunch of really smart algorithms for that sort of thing.

Answer 4

Once you get halfway there (once fact>num/2), your not going to discover any new numbers as the numbers above num/2 can be discovered by calculating num/fact for each one (this can also be used to easily print each number with its pair).

The following code should cust the time down by a few seconds on every calculation and cut it in half where num is odd. Hopefully you can follow it, if not, ask. I'll add more if I think of something later.

def even(num):
    '''Even numbers can be divided by odd numbers, so test them all'''
    fact=0
    while fact<num/2:
         fact+=1
         rem=num % fact
         if rem == 0:
              print '%s and %s'%(fact,num/fact)
def odd(num):
    '''Odd numbers can't be divided by even numbers, so why try?'''
    fact=-1
    while fact<num/2:
         fact+=2
         rem=num % fact
         if rem == 0:
              print '%s and %s'%(fact,num/fact)
while True:
    num=input(':')
    if  str(num)[-1] in '13579':
        odd(num)
    else:
        even(num)

Answer 5

Research integer factorization methods.

Answer 6

Yes. Use a quantum computer

Shor's algorithm, named after mathematician Peter Shor, is a quantum algorithm (an algorithm which runs on a quantum computer) for integer factorization formulated in 1994. Informally it solves the following problem: Given an integer N, find its prime factors.

On a quantum computer, to factor an integer N, Shor's algorithm runs in polynomial time (the time taken is polynomial in log N, which is the size of the input). Specifically it takes time O((log N)3), demonstrating that the integer factorization problem can be efficiently solved on a quantum computer and is thus in the complexity class BQP. This is exponentially faster than the most efficient known classical factoring algorithm, the general number field sieve, which works in sub-exponential time — about O(e1.9 (log N)1/3 (log log N)2/3). The efficiency of Shor's algorithm is due to the efficiency of the quantum Fourier transform, and modular exponentiation by squarings.

Answer 7

Unfortunately in Python, the divmod operation is implemented as a built-in function. Despite hardware integer division often producing the quotient and the remainder simultaneously, no non-assembly language that I'm aware of has implemented a /% or //% basic operator.

So: the following is a better brute-force algorithm if you count machine operations. It gets all factors in O(sqrt(N)) time without having to calculate sqrt(N) -- look, Mum, no floating point!

# even number

fact = 0
while 1:
    fact += 1
    fact2, rem = divmod(num, fact)
    if not rem:
        yield fact
        yield fact2
    if fact >= fact2 - 1:
        # fact >= math.sqrt(num)
        break