First n divisors of a number

Question

This is a very simple question but I'm having trouble with it. I'd like to create a method that shows the first n divisors of a given number x. I chose to create an array that stores all the multiples of x and you'd type how many you'd like to see.

E.g, if x = 20, then I'll have [1, 2, 4, 5, 10, 20] and the first 4 would be 1, 2, 4 and 5.

Here's what I wrote:

public static String multOf(int x, int n){

    int[] divisors = new int[n];

    for (int i = 0; i < divisors.length; i++){
        for (int j = 1; j < x + 1; j++){
            if (j % x == 0)
                divisors[i] = j;
        }
    }   

    return Arrays.toString(divisors);
}

I think there are better ways to do that but I'd like some tips on my solution.

Answer 1

The mistake is you loop the entire searching as many times as you need the result - once for every result. It is very expensive. Note the inner loop is the code and is needed to be looped just once. With each matched number to store, you can increment the index of an array to save the value.

1. You need to loop up to the half of the number.
2. You need to loop just once.

Here you go:

public static String multOf(int x, int n) {
    int[] result = new int[n];                // To store the result
    int count = 0;                            // A counter to not exceed the 'n'
    for (int i=1; i<Math.round(x/2); i++) {   // The iteration starting from the zero
        if (x % i == 0) {                     // Is 'x' divisible by 'i'?
            result[count] = i;                // ... if so, save to the array
            count++;                          // ... and increment the index
        } if (count == n) {                   // If the limit has been reached
            break;                            // ... leave the iteration
        }
    }
    return Arrays.toString(result);           // Return the result
}

However in case of the call such like multOf(20,9) when the number of divisors is smaller than required, the output would look like [1, 2, 4, 5, 0, 0, 0, 0, 0].

For this reason I recommend to use the List<Integer>:

public static String multOf(int x, int n) {
    List<Integer> list = new ArrayList<>();
    int count = 0;
    for (int i=1; i<Math.floor(x/2); i++) {
        if (x % i == 0) {
            list.add(i);
        } if (list.size() == n) {
            break;
        }
    }
    return list.toString();
}

Now, the multOf(20,9) call will result in [1, 2, 4, 5].

A true obsessed fan of Java 8 Stream API would do (yet, a bit slower):

public static String multOf(int x, int n) {
    return IntStream.rangeClosed(1, x/2)
                    .boxed()
                    .filter(i -> x % i == 0)
                    .limit(n)
                    .collect(Collectors.toList())
                    .toString();
}