代码之家 › 专栏 › 技术社区 › Richard Walton

Euler项目帮助(问题12)-主要因素等

java

Richard Walton · 技术社区 · 16 年前

我不想问,但我被困在这里了。

我需要测试一系列的数字来找到第一个超过500个因子: http://projecteuler.net/index.php?section=problems&id=12

-起初我试图强行给出答案(很长一段时间后找到一个480的数字)

-我现在正在研究确定一个数的素因子,然后用它们来找到所有其他因子。

我目前正处于这样一个阶段,我可以为我输入的任何数字获得一组素数因子-即300具有素数因子2 2 3 5 5

使用这个基本因子数组,我需要能够计算剩余的因子——这是我一直坚持的部分。基本上,据我所知,我需要计算数组中所有可能的数字组合…

即 2×2
2×2×3
2×2×3×5
2×3
2×3×3
…等等-但有趣的是…
2×5
2×3×5
…即数组中彼此不相邻的数字

我想不出一种方法来用通用的方式为任何长度的数组编写代码…

我需要帮助!我在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 回复 | 直到 10 年前

Martin 16 年前

据我所知,问题12没有提到素数吗?这就是你要看的那个吗?

三角形数的序列是由自然数加上…

如果是这样,那么不考虑素数会有帮助吗?;)

Steve Jessop 16 年前

好吧,第二次尝试,因为我让事情变得太困难了。

答案如下: 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。这是因为要成为一个因子,一个数字必须具有相同的素数,并提高到相同或更低的幂。

所以如果你知道基本因子,你只需要计算重复的因子,然后用上面的计算来计算因子的数量。

community wiki Chris Cooper 15 年前

可能已经晚了3个月了,但现在…

我看到答案2有给你所需要的答案的功能,但是在回答你最初的问题时,假设你出于某种原因需要,你如何产生所有的因素,下面是你如何做到的:

假设数组中有因子:

int[]素数=新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,所以你需要将你的集合筛选为不同的值。(哎呀,这比我想象的要长……:)

实现这一点的方法是使用两种方法,一种是选择递归的最大深度,启动递归并将最终结果Winnow,另一种是递归值:

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使用一个集合来确保我们只得到不同的值,然后将它们添加到一个列表中并进行排序,这样我们就可以按顺序显示这些因素。

当PermutaTimeFactors时,从零项(factor=1)到所有项(factor=1*2*2*3*5*5=300)生成。

希望有帮助。