Divisors inside an array

Question

I need to write a method that takes an array of integers and checks for every element if all its divisors (except the number itself and 1) are present in this array. If yes, the method will return true.

For example, the following array will return true:

4,5,10,2

I can't think of something efficient enough to be implemented. Could you guys help me out here?

I've been thinking to iterate through every element in the array, search for all of its divisors, put them on array, return the array and then compare to the elements in the original array.

This is a possible solution and it could work but I want to know of other possible solutions.

EDIT: Here is a code I've came up with but it is super slow. Could you guys help me optimise it a little bit?:

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

I think the following alogorithm solves your need. I have tested it on a few cases and it seems to work. For example the array:

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

executes instantly giving the answer "true". Try removing the 7 which will give the answer "false".

You call it thus:

reduce(set, 0, 0)

The principle used is to iterative recursively through the array, reducing the array through factorization of the array by each element. If you find an element which is smaller than the last factor, it means it can't be factored. This only works if the array is sorted. Once you reach the end of the array, you know all elements have been factored.

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);
        }

    }
}

See if it works, let me know if you run into any problems.

Answer 2

1.Iterate through every element in the array 2. Find in for loop its divisor 3. While doing 2), check for every divisor if it is contained in the array. If false - return false.