Finding a really big number

Question

So, I'm trying to find the largest prime factor of 600851475143. I have a simple method that finds the largest one currently which is this:

private static void findPrimeFactors(long num) {
        ArrayList<Long> list = new ArrayList<Long>();
        for (long i = 1; i <= num; i++) {
            int lol = 0;
            for (int a = 1; a < i; a++) {
                if (i % a == 0) {
                    lol++;
                }
            }
            if (lol < 2) {
                if (!list.isEmpty())
                    list.remove(list.size() - 1);
                list.add(i);
            }
        }
        System.out.println(list.get(list.size() - 1));
    }

Excuse me for my bad programming, I'm still learning. I figured that removed a lot of the entries from the list would cut down on the time to calculate it, so I removed the last entry unless it's the last one. I can do it with 100L which outputs the following:

97
Done in 1.0 milliseconds (0.001 seconds) (0.0625622 nano seconds)

And 20,000:

19997
Done in 1774.0 milliseconds (1.774 seconds) (177.3702774 nano seconds)

As you can see, it takes quite a bit longer to find it in a bigger number. Now I'm supposed to find the number I'm looking for in 600851475143, so I can say it's going to take a while to do. I'm wondering if their is any faster way to calculate this? This is all of my code:

import java.util.ArrayList;


public class Main {

    public static void main(String[] args) {
        try {
        long num = 600851475143L;
        long time = System.currentTimeMillis();
        long timeNano = System.nanoTime();

        findPrimeFactors(20000);

        double finishTime = System.currentTimeMillis() - time;
        double finishTimeNano = System.nanoTime() - timeNano;
        System.out.println("Done in " + finishTime + " milliseconds (" + ((finishTime) / 1000) + " seconds)" + " (" + finishTimeNano / 10000000 + " nano seconds)");
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    private static void findPrimeFactors(long num) {
        ArrayList<Long> list = new ArrayList<Long>();
        for (long i = 1; i <= num; i++) {
            int lol = 0;
            for (int a = 1; a < i; a++) {
                if (i % a == 0) {
                    lol++;
                }
            }
            if (lol < 2) {
                if (!list.isEmpty())
                    list.remove(list.size() - 1);
                list.add(i);
            }
        }
        System.out.println(list.get(list.size() - 1));
    }
}

Any tips on how to make this much faster is appreciated! Many of you may know that I'm doing this from Project Euler.

Answer 1

The first thing you have to understand is that, your task is essentially to "find ONE prime factor of a big number". If you know how to do it, you can divide your big number by the factor found and do a recurrence.

... but I regret to tell you that, there is NO known algorithm that finds a prime factor of a laaaaarge number in polynomial time. Actually, this is somehow the basis of a lot of cryptosystems (e.g. the famous RSA).

However, nowadays numbers of the size as 600851475143 can be broken down very quickly. There are a lot of algorithms that can do it - but you'll have to learn some math to understand them.

Just for this number, I can tell you that 600851475143 = 71 * 839 * 1471 * 6857.

Answer 2

If you are looking for the biggest factor you can start by the biggest number. Something like this (untested code):

private static void findPrimeFactors(long num) {
  long i;
  boolean candidate;
  for (i=num; i>1; i--){
    // i is candidate to be prime factor
    candidate=true;
    for (int a=2; candidate && a<i; a++){
      if (i % a == 0) candidate=false; // i is not prime.
    }
    if (candidate) break;
  }

  System.out.println(i);

}

Better performance can be achieved if you have a list of prime numbers and instead of testing every number from 2 to i, you only test the prime numbers that are less than i in the inner for.

import java.util.*;

public class PrimeFinder {

  private static List<Long> finder (Long max){
    List<Long> list=new ArrayList<Long>();
    Long maxPrime=2L;
    Long i;
    boolean candidate=true;
    for (i=2L;i<max;i++){
      candidate=true;
      for (Long prime:list){
        if (i % prime==0) {candidate=false;break;}
      }
      if (candidate){
        list.add(i);
        System.out.println(i+" "+list.size());
        maxPrime=i;
      }
    }

    System.out.println(maxPrime);
    return list;

  }

  public static void main(String[] argv){
    finder(600851475143L);
  }
}

Best algorithm seems to be sieve of atkin. It can be found here: Sieve of Atkin - Explanation and Java example

Answer 3

Tips to make it faster:

• You're trying to modify the ArrayList as you go, for array lists each time you do that is going to take O(n) time. If you really need to modify an list look at using linked list.
• You don't need to test all numbers, only the prime numbers.

Answer 4

You need a better algorithm. Here is a simple-minded implementation of trial division:

function factors(n)
  f, fs := 2, []
  while f * f <= n
    while n % f == 0
      append f to fs
      n := n / f
    f := f + 1
  if n > 1 append n to fs
  return fs

I'll leave it to you to translate that pseudocode to your favorite programming language, using appropriate data types. Note that 600851475143 is too large to store in a 32-bit integer, which is part of the fun of the problem.

If you're interested in solving the Project Euler problems that involve prime numbers, I modestly recommend the essay Programming with Prime Numbers at my blog.