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

Are you remembering to divide the number that you're factorizing by each factor as you find them?

Say, for example, you find that 2 is a factor. You can add that to your list of factors, but then you divide the number that you're trying to factorise by that value.

Now you're only searching for the factors of 150 billion. Each time around you should start from the factor you just found. So if 2 was a factor, test 2 again. If the next factor you find is 3, there's no point testing from 2 again.

And so on...

Answer 2

Finding prime factors is difficult using brute force, which sounds like the technique you are using.

Here are a few tips to speed it up somewhat:

• Start low, not high
• Don't bother testing each potential factor to see whether it is prime--just test LIKELY prime numbers (odd numbers that end in 1,3,7 or 9)
• Don't bother testing even numbers (all divisible by 2), or odds that end in 5 (all divisible by 5). Of course, don't actually skip 2 and 5!!
• When you find a prime factor, make sure to divide it out--don't continue to use your massive original number. See my example below.
• If you find a factor, make sure to test it AGAIN to see if it is in there multiple times. Your number could be 2x2x3x7x7x7x31 or something like that.
• Stop when you reach >= sqrt(remaining large number)

Edit: A simple example: You are finding the factors of 275.

1. Test 275 for divisibility by 2. Does 275/2 = int(275/2)? No. Failed.
2. Test 275 for divisibility by 3. Failed.
3. Skip 4!
4. Test 275 for divisibility by 5. YES! 275/5 = 55. So your NEW test number is now 55.
5. Test 55 for divisibility by 5. YES! 55/5 = 11. So your NEW test number is now 11.
6. BUT 5 > sqrt (11), so 11 is prime, and you can stop!

So 275 = 5 * 5 * 11

Make more sense?

Answer 3

Factoring big numbers is a hard problem. So hard, in fact, that we rely on it to keep RSA secure. But take a look at the wikipedia page for some pointers to algorithms that can help. But for a number that small, it really shouldn't be taking that long, unless you are re-doing work over and over again that you don't have to somewhere.

For the brute-force solution, remember that you can do some mini-optimizations:

• Check 2 specially, then only check odd numbers.
• You only ever need to check up to the square-root of the number (if you find no factors by then, then the number is prime).
• Once you find a factor, don't use the original number to find the next factor, divide it by the found factor, and search the new smaller number.
• When you find a factor, divide it through as many times as you can. After that, you never need to check that number, or any smaller numbers again.
• If you do all the above, each new factor you find will be prime, since any smaller factors have already been removed.

Answer 4

Here is an XSLT solution!

This XSLT transformation takes 0.109 sec.

<xsl:stylesheet version="2.0"
 xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
 xmlns:xs="http://www.w3.org/2001/XMLSchema"
 xmlns:saxon="http://saxon.sf.net/"
 xmlns:f="http://fxsl.sf.net/"
 exclude-result-prefixes="xs saxon f"
 >
 <xsl:import href="../f/func-Primes.xsl"/>

 <xsl:output method="text"/>


 <xsl:template name="initial" match="/*">
   <xsl:sequence select="f:maxPrimeFactor(600851475143)"/>
 </xsl:template>

 <xsl:function name="f:maxPrimeFactor" as="xs:integer">
   <xsl:param name="pNum" as="xs:integer"/>

   <xsl:sequence select=
    "if(f:isPrime($pNum))
       then $pNum
       else
         for $vEnd in xs:integer(floor(f:sqrt($pNum, 0.1E0))),
             $vDiv1 in (2 to $vEnd)[$pNum mod . = 0][1],
             $vDiv2 in $pNum idiv $vDiv1
           return 
             max((f:maxPrimeFactor($vDiv1),f:maxPrimeFactor($vDiv2)))
    "/>
 </xsl:function>
</xsl:stylesheet>

This transformation produces the correct result (the maximum prime factor of 600851475143) in just 0.109 sec.:

6857

The transformation uses the f:sqrt() and f:isPrime() defined in FXSL 2.0 -- a library for functional programming in XSLT. FXSL is itself written entirely in XSLT.

f:isPrime() uses Fermat's little theorem so that it is efficient to determine primeality.

Answer 5

One last thing nobody has mentioned, perhaps because it seems obvious. Every time you find a factor and divide it out, keep trying the factor until it fails.

64 only has one prime factor, 2. You will find that out pretty trivially if you keep dividing out the 2 until you can't anymore.

Answer 6

$ 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 7

The key to understanding why the square root is important, consider that each factor of n below the square root of n has a corresponding factor above it. To see this, consider that if x is factor of n, then x/n = m which means that x/m = n, hence m is also a factor.

Answer 8

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 9

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 10

The fastest algorithms are sieve algorithms, and are based on arcane areas of discrete mathematics (over my head at least), complicated to implement and test.

The simplest algorithm for factoring is probably (as others have said) the Sieve of Eratosthenes. Things to remember about using this to factor a number N:

• general idea: you're checking an increasing sequence of possible integer factors x to see if they evenly divide your candidate number N (in C/Java/Javascript check whether N % x == 0) in which case N is not prime.
• you just need to go up to sqrt(N), but don't actually calculate sqrt(N): loop as long as your test factor x passes the test x*x<N
• if you have the memory to save a bunch of previous primes, use only those as the test factors (and don't save them if prime P fails the test P*P > N_max since you'll never use them again
• Even if you don't save the previous primes, for possible factors x just check 2 and all the odd numbers. Yes, it will take longer, but not that much longer for reasonable sized numbers. The prime-counting function and its approximations can tell you what fraction of numbers are prime; this fraction decreases very slowly. Even for 2⁶⁴ = approx 1.8x10¹⁹, roughly one out of every 43 numbers is prime (= one out of every 21.5 odd numbers is prime). For factors of numbers less than 2⁶⁴, those factors x are less than 2³² where about one out of every 20 numbers is prime = one out of every 10 odd numbers is prime. So you'll have to test 10 times as many numbers, but the loop should be a bit faster and you don't have to mess around with storing all those primes.

There are also some older and simpler sieve algorithms that a little bit more complex but still fairly understandable. See Dixon's, Shanks' and Fermat's factoring algorithms. I read an article about one of these once, can't remember which one, but they're all fairly straightforward and use algebraic properties of the differences of squares.

If you're just testing whether a number N is prime, and you don't actually care about the factors themselves, use a probabilistic primality test. Miller-Rabin is the most standard one, I think.

Answer 11

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 12

The specific number is 300425737571? It trivially factors into 131 * 151 * 673 * 22567. I don't see what all the fuss is...

Answer 13

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 14

You could use the sieve of Eratosthenes to find the primes and see if your number is divisible by those you find.

Answer 15

You only need to check it's remainder mod(n) where n is a prime <= sqrt(N) where N is the number you are trying to factor. It really shouldn't take over an hour, even on a really slow computer or a TI-85.

Answer 16

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

Answer 17

Just to expand/improve slightly on the "only test odd numbers that don't end in 5" suggestions...

All primes greater than 3 are either one more or one less than a multiple of 6 (6x + 1 or 6x - 1 for integer values of x).

Answer 18

It shouldn't take that long, even with a relatively naive brute force. For that specific number, I can factor it in my head in about one second.

You say you don't want solutions(?), but here's your "subtle" hint. The only prime factors of the number are the lowest three primes.

Answer 19

Semi-prime numbers of that size are used for encryption, so I am curious as to what you exactly want to use them for.

That aside, there currently are not good ways to find the prime factorization of large numbers in a relatively small amount of time.