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

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

Answer 2

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 3

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 4

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 5

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 6

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?