查找假数的所有因子

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

示例。如果你加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

来源

2014-09-04 Neoaptt

这是一个项目欧拉问题？ – wvdz 2014-09-04 15:00:21

顺便说一句，你只是分解偶数（你确定Phony Numbers都是偶数？）。你可以筛分直到“Sqrt（Limit）”，将数字素数分解并使用素数因子分解生成除数。也可以在素数中添加因式分解缓存。 – NetVipeC 2014-09-04 15:33:21

这些数字被称为完美数字，而不是假数字，你可以通过搜索整数序列的在线百科全书来找到6,28,496,8128。唯一的完美数字的形式是2 * 2^n *（2^n-1）其中2^n-1是素数，它是一个着名的开放问题，是否存在奇数的完美数字，并且您不会通过小数字的蛮力搜索找到任何数字。对数字进行因子分解的方法要比试验分部快得多，或者甚至是测试可能的素数因子至sqrt（n）的更好方法，但其中很多都是复杂的。例如，尝试Pollard-rho因子分解。 – 2014-09-04 17:27:23

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

您的主要储蓄虽然可以来自您的factoring方法 - 您知道num/2以上的数字不能成为因素，因此只要您到达那里，您就可以停下来。

（事实上，在这种情况下，你可以停在num/3因为你跳过2

来源

2014-09-04 14:47:52

当你通过迭代我相信你可以做师取得共同的因素，以及对于例如：

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

但你必须考虑到已经加入他们，所以我还不能肯定它是否有助于从长远来看

您还可以使用：

return num == sum

来源

2014-09-04 14:53:18 FintanH

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

来源

2014-09-04 16:14:09 user2566092

查找假数的所有因子

回答

相关问题