java计算素数因子分解的更有效方法？

Question

我现在有一个程序来寻找一个给定数字的素因子分解；对于较小的数字来说效果很好，但对于任何超过一百万的数字来说都需要时间。我的代码效率极低，查找输入下面的所有素数，并检查哪些素数被除而没有余数。我不知道如何降低效率，有什么帮助吗

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;
}

Answer 1

从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;
  }

Answer 2

改进代码的一种方法是删除循环结构中的IO。 就是

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;
}

我相信单凭这一点，你就会看到巨大的性能提升

Answer 3

坚持你的通用算法，而不是重新编写primesBelow(..)方法：我想说：

1. 一旦divides = true，就可以跳出for循环
2. 用于素性检查的复杂for循环终止条件可以简化为Math.sqrt(n)——我不会进行数学运算，但您可以自己查找