查找虚假数字的所有因素

Question

我正在努力寻找最快的全因子算法。我使用把所有的因素放在一个数组表中进行加法，并将其与原始数字进行比较，以确定它们是否相同。

举例说明。如果添加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

Answer 1

有几件小事跳出来了:您的比较方法是没有意义的，删除它，它将简化您的代码。您的求和方法可以只使用+=。为什么循环遍历每一个数字，然后删除其中的一半，只需在循环上使用-=2。

但是，您的主要储蓄可以来自您的factoring方法--您知道num/2上的数字不能是因素，所以您可以在到达那里后立即停止。

(实际上，在本例中，您可以在跳过2时在num/3停下来。

Answer 2

当你在迭代的时候，我相信你也可以通过除法得到辅助因子。例如：

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

但你必须考虑已经添加了他们，所以我不是积极的，如果这有助于长期。

您还可以使用：

return num == sum

Answer 3

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