Prime factor of 300 000 000 000?

Question

I need to find out the prime factors of over 300 billion. I have a function that is adding to the list of them...very slowly! It has been running for about an hour now and i think its got a fair distance to go still. Am i doing it completly wrong or is this expected?

Edit: Im trying to find the largest prime factor of the number 600851475143.

Edit: Result:

{
    List<Int64> ListOfPrimeFactors = new List<Int64>();
    Int64 Number = 600851475143;
    Int64 DividingNumber = 2;

    while (DividingNumber < Number / DividingNumber)
    {
        if (Number % DividingNumber == 0)
        {
            ListOfPrimeFactors.Add(DividingNumber);
            Number = Number/DividingNumber;
        }
        else
            DividingNumber++;
        }
        ListOfPrimeFactors.Add(Number);
        listBox1.DataSource = ListOfPrimeFactors;
    }
}

Answer 1

I wouldn't expect it to take very long at all - that's not a particularly large number.

Could you give us an example number which is causing your code difficulties?

Answer 2

Here's some Haskell goodness for you guys :)

primeFactors n = factor n primes
  where factor n (p:ps) | p*p > n = [n]
                        | n `mod` p /= 0 = factor n ps
                        | otherwise = p : factor (n `div` p) (p:ps)
        primes = 2 : filter ((==1) . length . primeFactors) [3,5..]

Took it about .5 seconds to find them, so I'd call that a success.

Answer 3

$ time factor 300000000000 > /dev/null

real        0m0.027s
user        0m0.000s
sys         0m0.001s

You're doing something wrong if it's taking an hour. You might even have an infinite loop somewhere - make sure you're not using 32-bit ints.

Answer 4

Here's one site where you can get answers: Factoris - Online factorization service. It can do really big numbers, but it also can factorize algebraic expressions.

Answer 5

I spent some time on this since it just sucked me in. I won't paste the code here just yet. Instead see this factors.py gist if you're curious.

Mind you, I didn't know anything about factoring (still don't) before reading this question. It's just a Python implementation of BradC's answer above.

On my MacBook it takes 0.002 secs to factor the number mentioned in the question (600851475143).

There must obviously be much, much faster ways of doing this. My program takes 19 secs to compute the factors of 6008514751431331. But the Factoris service just spits out the answer in no-time.

Answer 6

Your algorithm must be FUBAR. This only takes about 0.1s on my 1.6 GHz netbook in Python. Python isn't known for its blazing speed. It does, however, have arbitrary precision integers...

import math
import operator

def factor(n):
    """Given the number n, to factor yield a it's prime factors.
    factor(1) yields one result: 1. Negative n is not supported."""
    M = math.sqrt(n)  # no factors larger than M
    p = 2             # candidate factor to test
    while p <= M:     # keep looking until pointless
        d, m = divmod(n, p)
        if m == 0:
            yield p   # p is a prime factor
            n = d     # divide n accordingly
            M = math.sqrt(n)  # and adjust M
        else:
            p += 1    # p didn't pan out, try the next candidate
    yield n  # whatever's left in n is a prime factor

def test_factor(n):
    f = factor(n)
    n2 = reduce(operator.mul, f)
    assert n2 == n

def example():
    n = 600851475143
    f = list(factor(n))
    assert reduce(operator.mul, f) == n
    print n, "=", "*".join(str(p) for p in f)

example()

# output:
# 600851475143 = 71*839*1471*6857

(This code seems to work in defiance of the fact that I don't know enough about number theory to fill a thimble.)