Decreasing run time of code [closed]

Closed. This question needs to be more focused. It is not currently accepting answers.

---

Want to improve this question? Update the question so it focuses on one problem only by editing this post.

Closed 8 years ago.

Improve this question

How can I make this code run faster?

public class ProjectEuler3 {
    public static void main(String[] args) {
        System.out.println(findfactors(600851475143l));
    }

    public static long findfactors(long n) {
        long[] factors = new long[1000000];
        int nooffactor = 0;

        int c = 0;

        for (lo开发者_JAVA百科ng i = 2; i < n; i++) {
            if (findPrime(i)) {
                factors[c++] = i;
                nooffactor++;
            }
        }

        return factors[nooffactor - 1];
    }

    public static boolean findPrime(long n) {
        for (long i = 2; i < n; i++) {
            if(n % i == 0)
                return false;
        }
        return true;
    }
}

---

I'm not exactly sure what this particular problem is asking for, but one performance boost would be to improve your primality test. Right now, you are checking from 2 to n. However, you only need to check from 2 to sqrt(n), which will greatly reduce the numbers you check when n is a large number. You can also not check even values greater than 2.

It's still simple, but this should yield a performance boost, especially for larger n:

public static boolean findPrime(long n){
    int max = (int) Math.ceil(Math.sqrt(n))
    for(long i=2; i<max; i++){
        if(n%i == 0) {
            return false;
        }
    }
    return true;
}

Depending on exactly what you are trying to do, though, there might be better solutions, such as a totally different approach to the problem (see Matt Ball's suggestion of a totally different factoring algorithm). I'm just looking at your code and trying to reduce the number of operations without a significant change in strategy.

---

Consider remembering primes when they have been calculated.

---

By researching factorization algorithms.

---

You could try something like this.

private static final BitSet IS_PRIME = new BitSet(); static {
    IS_PRIME.set(2);
}

private static int IS_PRIME_LIMIT = 2;

public static boolean isPrime(int n) {
    int p = IS_PRIME_LIMIT;
    while (p < n) {
        p++;
        IS_PRIME.set(p);
        if (p % 2 == 0) {
            IS_PRIME.clear(p);
        } else {
            for (int i = 3; i * i <= p; i += 2)
                if (IS_PRIME.get(i) && p % i == 0) {
                    IS_PRIME.clear(p);
                    break;
                }
        }
    }
    IS_PRIME_LIMIT = p;
    return IS_PRIME.get(n);
}

public static List<Integer> findfactors(long n) {
    List<Integer> ret = new ArrayList<Integer>();
    int sqrtN = (int) Math.sqrt(n);

    for (int i = 2; n > 1 && i <= sqrtN; i++) {
        if (isPrime(i)) {
            while (n > 1 && n % i == 0) {
                n /= i;
                ret.add(i);
            }
        }
    }
    if (n > 1)
        ret.add((int) n);
    return ret;
}

public static void main(String... args) {
    // warm up
    for(int i=0;i<10000;i++)
        findfactors(600851475143L);

    //  time one lookup.
    long start = System.nanoTime();
    List<Integer> factors = findfactors(600851475143L);
    long time = System.nanoTime() - start;
    System.out.println(factors);
    System.out.printf("Took %.3f ms to find factors%n", time/1e6);
}

prints

[71, 839, 1471, 6857]
Took 0.051 ms to find factors

---

if two is a factor then you can keep dividing n by two until it's not divisible. This applies to the other numbers as well. This reduces the length of the loop drastically.

Precalculating all the primes up to sqrt(n) would also help.

---

Actually the key thing to notice is that you don't need to go all the way up to your original dividend. When you find a factor, you divide your dividend by that factor (as many times as necessary), then increase the divisor. This will be very fast so long as the number doesn't happen to have some huge prime factor (unlikely).

Technically you only need to search up to the square root, but for your purposes it won't make much difference if you do what I said above.

Here is a Scala implementation:

  def lpf(n: Long, f: Long): Long = {    // Largest prime factor function, n = dividend, f = trial divisor
    if (f * f > n) n                     // If divisor squared is bigger than dividend, we have the answer
    else if (n % f == 0) lpf(n / f, f)   // If it divides exactly, divide through and try again with same factor
    else lpf(n, f + 1)                   // Otherwise increase divisor
  }
  println(lpf(600851475143L, 2))         // Completes in 1.6 milliseconds