0

我正在尝试找到最快的全因子算法。我使用将所有因素放入数组列表中进行加法，并将总和与原始数字进行比较，以确定它们是否相同。

例子。如果加上 1+2+3 = 6，则 6 的因数为 [1,2,3}。

除了我现在拥有的程序之外，还有更快的方法来分解、添加和比较吗？

public class Phony_Number {

private int number;

public Phony_Number(int num) {
    number = num;
    print();
}

public Phony_Number() {
    number = 0;
}

private ArrayList<Integer> factoring(int num) {
    ArrayList<Integer> factors = new ArrayList<Integer>();
    if (num % 2 == 0) {
        for (int ff = 3; ff < num; ff++) {
            if (num % ff == 0) {
                factors.add(ff);
            }
        }
    }
    return factors;
}

private int sum(ArrayList<Integer> array) {
    int sum = 0;
    for (int i = 0; i < array.size(); i++) {
        sum = +sum + array.get(i);
    }
    return sum+3;
}

private boolean compare(int num, int sum) {
    if (num == sum)
        return true;
    return false;
}

public void print() {
    for (int i = number; i > 5; i--) {
        if (compare(i, sum(factoring(i)))) {
            System.out.println("Number " + i + " is phony number");
        }
    }
}

}

My current result for 20,000 numbers is this

Number 8128 is phony number

Number 496 is phony number

Number 28 is phony number

Number 6 is phony number

Nano RunTime 359624716
4

3 回答 3

1

一些小事情跳了出来：您的比较方法毫无意义，删除它，它会简化您的代码一点。您的 sum 方法可以只使用 +=。为什么要遍历每个数字然后删除其中的一半，只需在循环中使用 -=2 即可。

不过，您的主要节省可能来自您的factoring方法——您知道超出的数字num/2不是因素，因此您可以在到达那里后立即停止。

（事实上​​，在这种情况下，您可以在num/3跳过 2 时停下来。

于 2014-09-04T14:47:52.660 回答
1

当您进行迭代时，我相信您也可以通过除法获得共同因素。例如：

if (num % ff == 0) 
{
   factors.add(num/ff)
   factors.add(ff);
}

但是您必须考虑已经添加它们，所以从长远来看，我不肯定它是否有帮助。

您还可以使用：

return num == sum
于 2014-09-04T14:53:18.280 回答
1

num 的除数 ff 成对出现，即如果 ff 是除数，则 ff 和 num/ff 都是除数。此外，除非 ff*ff == num，否则该对中的除数是不同的。因此，您将循环条件更改为 ff*ff <= num，然后如果 ff 除以 num，则将 ff 添加到因子列表中，如果 ff*ff != num 也添加 num/ff。这将使您的程序以 num 时间的平方根运行，而不是 num 时间。

于 2014-09-04T16:14:09.787 回答