HiveBrain v1.2.0
Get Started
← Back to all entries
patternpythonMinor

Attempting to efficiently compute the largest prime factor

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
efficientlythecomputelargestattemptingfactorprime

Problem

I'm working on the third Euler problem and I've written a simple little function that returns the list of prime factors of a given number.

The number for which I have to get all the factors is over 6 billion, so building this huge freakin list of numbers in memory struck me as wonky.

I decided I'd build a factor function that generates output by the chunk and spits it out so that I can write it to a text file chunk by chunk. A buffered_factor function:

Ok, I've decided that doing the 'buffered' thing isn't needful. The computation is just going to take a while, and making my factor function a generator will keep my program light in memory.

I'm looking for best practices and practical advice about (what I think is describable as) buffering the output of a function.

Here's the prime sieve:

def is_prime(n):
    if n == 1:
        return False
    if n == 2:
        return True

    for i in range(2, int(math.ciel(math.sqrt(n))):
        if n % i:
            return False
        return True


And the factoratorizer:

def factor(num):
    """Get factors of given number.

    :param num: get us them there factors o this number here
    :type num: integer
    :param chunk_size: number of operations to work through before crapping out a list
    :rtype: list of factors
    :raises: ValueError on num = 1, please' % num)

    for i in (n + 1 for n in xrange(num)):
        if num % i == 0:
            if is_prime(i):
                yield i


I'm trying to use it thusly:

import os
from factor import factor
TARGET = 600851475143
OUTFILE = 'factors.txt'

with open(OUTFILE, 'w') as f:
   for output in buffered_factor(TARGET):
       f.write(str(output))
       f.flush()


Nothing's being written to file, so obviously I'm doing something wrong.

Solution

Some advice about maths and algorithms which will be useful for this problem and for future problems:

-
You are interested in prime factors.

-
You don't care about the non-biggest factors (you might go through them but there is not much point in storing them).

-
If a number n can be decomposed in n = m*p then at least one of m and p is smaller than sqrt(n).

Context

StackExchange Code Review Q#31661, answer score: 2

Revisions (0)

No revisions yet.