java - 使用嵌套数组显示和计算质因数或其他运算的数量

Question

我有一个算法可以计算给定数字范围的素因数。 例如 10 到 20 之间。

结果是:数字 10:因数为:2、5。数字 11:因数为:11。数字 12:因数为:2、6。等等...。

但是我想检查哪些数字只有 2 个或 3 个或 4 个或更多质因数。

我存储在数组中的那些数字。我的想法是将这些单独的质因数分配给给定的数字。所以我可能应该有一个数组列表，它是动态变化的(名称和大小也是如此)。

例如:

ArrayOfNumbers[0] = 10;
ArrayOfPrimeFactorsOf10Number[0] = 2; ArrayOfPrimeFactorsOf10Number[1] = 5;

ArrayOfNumbers[1] = 11; ArrayOfPrimeFactorsOf11Number[0] = 11;

我可以比较哪个数字有 2 或 3 个质因数 => 通过获取属于多个数组 (ArrayOfNumbers) 的质因数数组 (ArrayOfPrimeFactorsOf..Number) 的大小，并显示该数字及其质因数。

我的问题是:如何将其作为嵌套数组 (ArrayOfPrimeFactorsOf..Number) 并将其分配给 ArrayOfNumbers[..]？

也许您还有其他想法来解决这一挑战吗？

下面是一个程序:

 public static void countPrimeFactors() {

    int min = 10; // min number in array
    int max = 20; // max number in array

    Integer[] arrayOfNumbers = new Integer[100000];

    for (int a = 0; a < arrayOfNumbers.length; a++) {

        for (int k = min; k <= max; k++) {

            arrayOfNumbers[a] = k;
            System.out.print(arrayOfNumbers[a] + ": ");

            if (arrayOfNumbers[a] % 2 == 0) {

                System.out.print(2 + " ");
                arrayOfNumbers[a] /= 2;

            }
        // n must be odd at this point. So we can
        // skip one element (i = i +2)
            // i is a current factor
            // array[a] is a current number

        for (int i = 3; i <= Math.sqrt(arrayOfNumbers[a]); i += 2) {
            // While i divides n, print i and divide n
            if (arrayOfNumbers[a] % i == 0) {

                System.out.print(i + " ");
                arrayOfNumbers[a] /= i;
            }

        }

        // This condition is to handle the case when
        // n is a prime number greater than 2
        if (arrayOfNumbers[a] > 2)

            System.out.print(arrayOfNumbers[a] + " , ");

        }  
        break;
    }

    System.out.print("Length of array[a]: " + arrayOfNumbers.length);
}

Answer 1

我认为使用 map 是最好的解决方案，尤其是 TreeMap，键应​​该是您正在查找因子的数字，值应该是包含所有因子的其他集合。示例:

    Map<Integer, Set<Integer>> numbers = new TreeMap<>();
            int min = 10;
    int max = 20;
    Map<Integer, Set<Integer>> numbers = new TreeMap<>();
    for (int i = min; i <= max; i++) {
        Set<Integer> factors = new TreeSet<>();
        for (int j = 2; j <= i/2; j++) {
            if (i % j == 0) {
                factors.add(j);
            }
        }
        //factors.add(i);
        numbers.put(i, factors);

    }
    System.out.println(numbers.get(11).size());
    System.out.println(numbers.values());

这是一般想法，您可以通过numbers.get(someNumber).size();轻松获得每个数字的因子数。

如果取消注释factors.add(i);那么我们正在寻找因子的数字也会被计算在内，如果您需要这样的话。

迭代

  // Iterator mapIt = numbers.keySet().iterator(); - you can only iterate thru map by using iterator

    for(int i = min; i <= max; i++){
        Iterator it = numbers.get(i).iterator();
        System.out.print("Iterating for number " + i+": ");
        while(it.hasNext()){
            System.out.print(it.next()+" ");
        }
        System.out.println();
    }

这应该给你一个总体的想法，如果你不喜欢使用迭代器，那么使用 ArrayList而不是 Set，例如 Map<Integer, List<Integer>>