java - 数组内的除数

Question

我需要编写一个方法，它接受一个整数数组并检查每个元素的所有除数(数字本身和 1 除外)是否都存在于该数组中。如果是，该方法将返回 true。

例如，下面的数组将返回 true:

4,5,10,2

我想不出可以实现的高效方法。你们能帮帮我吗？

我一直在考虑遍历数组中的每个元素，搜索它的所有除数，将它们放在数组中，返回数组，然后与原始数组中的元素进行比较。

这是一个可能的解决方案，它可以工作，但我想知道其他可能的解决方案。

编辑:这是我想出的代码，但速度非常慢。你们能帮我优化一下吗？:

import java.util.Arrays;

public class Divisors {

        public static void main(String[] args) {
                int[] numbers = { 4, 5, 10, 2 };
                boolean flag = true;
                for (int num : numbers) {
                        if (num % 2 != 0) {
                                for (int subNum = 1; subNum < num / 2; num += 2) {
                                        if(num%subNum == 0 && subNum != 1) {
                                                if(!Arrays.asList(numbers).contains(subNum)) {
                                                        flag = false;
                                                }
                                        }
                                }
                        } else {
                                for (int subNum = 1; subNum < num / 2; num++) {
                                        if(num%subNum == 0 && subNum != 1) {
                                                if(!Arrays.asList(numbers).contains(subNum)) {
                                                        flag = false;
                                                }
                                        }
                                }
                        }
                }

                System.out.println("Result is: "+flag);
        }
}

Answer 1

我认为以下算法可以解决您的需求。我已经在几个案例中对其进行了测试，它似乎有效。例如数组:

int[] set = {2, 3, 4, 5, 7, 10, 11, 15, 18, 35};  

立即执行给出答案“真”。尝试删除答案为“false”的 7。

你这样调用它:

reduce(set, 0, 0)

使用的原理是递归迭代数组，通过每个元素分解数组来减少数组。如果你发现一个元素小于最后一个因子，这意味着它不能被分解。这仅在数组已排序时有效。一旦到达数组末尾，您就知道所有元素都已分解。

private static boolean reduce (int[] set, int index, int factor) {
    // NOTE: set must be a sorted set of integers
    if (index == set.length) {
        return true;
    } else {
        int divisor = set[index];
        if (divisor != 1) {
            if (divisor < factor) return false;
            for (int i = index; i < set.length; i++) {
                while ((set[i]%divisor) == 0) {
                set[i] = set[i]/divisor;
                }
            }
            return reduce(set, index+1, divisor);
        } else {
            return reduce(set, index+1, factor);
        }

    }
}

看看它是否有效，如果您遇到任何问题，请告诉我。