java - 如何获得两个数字之间的最大质因数并将它们存储在数组中？

Question

我被要求解决这个问题:

Write a function that takes two numbers n1 and n2 as input (with n2>n1) and returns an array of largest prime factors corresponding to each number between n1 and n2.

我的尝试如下所示，但我的代码无法正常工作。它不是从 n1 迭代到 n2。我怎样才能做对呢？

public static class A{
        static int testcase1=5;
        static int testcase2=10;

        public static void main(String args[]){
            A testInstance = new A();
            int[] result = testInstance.getLpfd(testcase1,testcase2);
            System.out.print("{");
            for (int i=0;i<result.length;i++){
                if (i>0)
                    System.out.print(",");
                System.out.print(result[i]);
            }
            System.out.println("}");
        }

        public int[] getLpfd(int n1,int n2){
            int current=0;
            int[] factors = new int[20];
            for(int j=n1;j<=n2;j++){
                for (int i = 2; i <= j; i++){
                    while(j % i == 0){
                        factors[current]=i;
                        j /= i;
                        current++;
                    }
                }
            }           
            return factors;
        }
    }
}

Answer 1

将查找因子的任务与写入最大因子的任务分开是最简单的。这是一个查找因子的函数:

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

按降序返回n的因子，因此最大的因子位于列表的头部。然后很容易积累一个范围内最大质因数的列表:

function lpf(lo, hi)
    result := makeArray(0 .. hi-lo)
    for n from lo to hi
        result[n-lo] := head(factors(n))
    return result

我将把它翻译成 Java。

如果您的范围很大，埃拉托斯特尼筛法的变体将比计算所有这些因子快得多。