Euler项目帮助(问题12) -主因子等
我不想问，但我被困在这里了。
我需要测试一个数字序列来找到第一个有超过500个因子的数字：http://projecteuler.net/index.php?section=problems&id=12
-At首先，我尝试暴力破解答案(很长一段时间后找到一个480的数字)
-I现在正在考虑确定一个数的质因数，然后使用它们来找出所有其他因子。
我目前所处的阶段是，对于我输入的任何数字，我都可以得到一个素数因数数组--即300的素数因数为2 2 3 5 5
使用这个主因子数组，我需要能够计算剩余的因子-这是我坚持的部分。基本上，据我所知，我需要计算数组中所有可能的数字组合...
即2*2
2*2*3
2*2*3*5
2*3
2*3*3
...and等等--但是有趣的是像这样的东西...
2*5
2*3*5
数组中彼此不相邻的...i.e编号
我想不出一种方法来对任何长度数组以通用的方式进行编码。
我需要帮助！附注:我在Java工作
编辑:我的暴力破解代码-正如有人建议的那样，暴力破解问题将会起作用，所以我的代码中可能有一个错误:(
package euler.problem12;
public class Solution {
public static void main(String[] args) {
int next = 1;
int triangle = 0;
int maxFactors = 0;
while(true) {
triangle = triangle + next;
int factors = 1;
int max = (int) triangle / 2;
for(int i = 1; i <= max; ++i) {
if(triangle % i == 0) {
factors ++;
}
}
if(factors > maxFactors) {
maxFactors = factors;
System.out.println(triangle + "\t" + factors);
}
next++;
}
}
}回答 3
Stack Overflow用户
发布于 2008-11-10 08:43:00
据我所知，问题12没有提到任何关于质数的内容？这就是你要看的那个吗？
三角形数序列是通过将自然数相加生成的。
如果是这样，那么也许不考虑质数会有所帮助？;)
Stack Overflow用户
发布于 2008-11-10 10:00:37
好的，第二次尝试，因为我把事情搞得太难了。
答案在这里：http://mathforum.org/library/drmath/view/57151.html
如果你将一个数字分解到它的素数幂因数中，那么因子的总数就是将所有指数相加，然后将这些结果相乘得到的。示例: 108 = 2^2 * 3^3，因此因子总数为(2+1) * (3+1) =3* 4 = 12。可以肯定的是，108的因子是1、2、3、4、6、9、12、18、27、36、54和108。这是因为要成为一个因子，一个数必须具有相同的质数，并提高到相同或更低的幂。
因此，如果你知道素因子，你只需要计算重复的因子，并使用上面的计算来计算出因子的数量。
Stack Overflow用户
发布于 2009-03-03 09:53:23
可能已经晚了3个月了，但是现在开始...
我看到答案二提供了给你所需要的答案的函数，但在回答你最初的问题时，你假设出于某种原因，你需要生成所有的因子，那么这里是你如何做到的：
假设您在一个数组中具有以下因子：
int[] primeFactors =新int[] {2，2，3，5，5}；
您需要做的是为每个可能的深度递归每个按顺序排列，然后将结果集减少为唯一值。
我将解释我的意思：“按顺序排列”：假设你从数组的位置0开始，下一个元素必须是1，2，3或4，如果你从1开始，那么下一个元素一定是2，3或4，依此类推。
“每个可能的深度”：每个单一因素，然后是任何两个因素，然后是任何三个因素，依此类推，直到你得到所有五个因素。
“缩减集合”：如果你有两个元素，比如0&3，0&4，1&3或1&4，它们都给你2*5= 10，它们都提供了因子10，所以你需要把你的集合筛选成不同的值。(呼，这比我预想的要长...：)
这样做的方法是使用两种方法，一种是选择递归的最大深度，启动递归并筛选最终结果，另一种是递归值：
public static void main(String[] args) {
int[] primeFactors = new int[] {2, 2, 3, 5, 5};
List<Integer> allFactors = getAllFactors(primeFactors);
for (int factor : allFactors) {
System.out.println("Factor: " + factor);
}
}
private static List<Integer> getAllFactors(int[] primeFactors) {
Set<Integer> distinctFactors = new HashSet<Integer>();
for (int maxDepth = 0; maxDepth <= primeFactors.length; maxDepth++) {
permutatPrimeFactors(0, maxDepth, 0, 1, primeFactors, distinctFactors);
}
List<Integer> result = new ArrayList<Integer>(distinctFactors);
Collections.sort(result);
return result;
}
private static void permutatPrimeFactors(int depth, int maxDepth, int minIndex, int valueSoFar, int[] primeFactors, Set<Integer> distinctFactors) {
if (depth == maxDepth) {
distinctFactors.add(valueSoFar);
return;
}
for (int index = minIndex; index < primeFactors.length; index++) {
permutatPrimeFactors(depth + 1, maxDepth, index + 1, valueSoFar * primeFactors[index], primeFactors, distinctFactors);
}
}getAllFactors使用一个集合来确保我们只获得不同的值，然后将它们添加到一个列表中并对其进行排序，以便我们可以按顺序显示因子。
而permutatPrimeFactors，则从零项(因子= 1)生成到所有项(因子=1*2*2 *3 *5*5= 300)。
希望这能有所帮助。
https://stackoverflow.com/questions/277368
复制相似问题
腾讯云开发者
