CODEWITHSUNDEEP
java
platelminto
platelminto

Reputation: 358

More efficient way of calculating prime factorisation?

I currently have a program to find the prime factorisation of a given number; works fine with smaller numbers, but it takes ages for anything over a million. My code is extremely inefficient, finding all prime numbers below the input and checking which ones divide without a remainder. I don't know how to make it less inefficient, any help?

static ArrayList<Integer> primeNumbersBelow(long n) {

    ArrayList<Integer> ay = new ArrayList<Integer>();
    ay.add(2);

    for(int i = 3; i < ((n % 2 != 0) ? (n + 1) / 2 : n / 2); i++) {
        boolean divides = false;
        for(int j = 2; j < i; j++) {
            if(i % j == 0) {
                divides = true;
            }
        }
        if(!divides) {
            ay.add(i);
            System.out.println(i);
        }
    }
    return ay;
}

static ArrayList<Integer> primeFactorisationOf() {

    ArrayList<Integer> ay = new ArrayList<Integer>();
    ArrayList<Integer> aay = primeNumbersBelow(input);
    long n = input;

    for(int i = 0, len = aay.size(); i < len; i++) {
        int f = aay.get(i);
        boolean run = true;

        while(run) {
            if(n % f == 0) {
                ay.add(f);
                n /= f;
            } else {
                run = false;
            }
        }
    }
    return ay;
}

Upvotes: 0

Views: 79

Answers (3)

Chrstfer CB
Chrstfer CB

Reputation: 75

One way to improve the code is to remove the IO inside your loop structure. That is, 

static ArrayList<Integer> primeNumbersBelow(long n) {
    ArrayList<Integer> ay = new ArrayList<Integer>();
    ay.add(2);

    for(int i = 3; i < ((n % 2 != 0) ? (n + 1) / 2 : n / 2); i++) {
        boolean divides = false;
        for(int j = 2; j < i; j++) {
            if(i % j == 0) {
                divides = true;
            }
        }
        if(!divides) {
            ay.add(i);
            //REMOVE THE FOLLOWING LINE
            System.out.println(i);
        }
    }
    return ay;
}

I'm sure you'll see a huge performance boost just from that alone.

Upvotes: 0

Amir Afghani
Amir Afghani

Reputation: 38561

Sticking to your general algorithm and not re-writing your primesBelow(..) method: I would say:

  1. Once divides = true, you can break out of the for-loop
  2. The complex for loop termination condition for primality check can be reduced to the Math.sqrt(n) - I won't go through the math, but you can look that up yourself.

Upvotes: 0

Jordi Castilla
Jordi Castilla

Reputation: 27003

From Mr Lars Vogel @ vogella...

 public static List<Integer> primeFactors(int number) {
    int n = number;
    List<Integer> factors = new ArrayList<Integer>();
    for (int i = 2; i <= n; i++) {
      while (n % i == 0) {
        factors.add(i);
        n /= i;
      }
    }
    return factors;
  }

Upvotes: 1

Related Questions