This code finds all the divisors of a given number. Can it be shortened?

import java.util.Scanner;

public class PrimeNum2{
    public static void main(String args[]){
        Scanner x=new Scanner(System.in);
        System.out.print("Enter the number :  ");
        long y=x.nextInt(),i;
        System.out.print("Divisors of "+y+" = 1 , ");

        for( i=2;i<y;i++){
            long z=y%i;
            if(z!=0)continue;
                System.out.print(i+" , ");

        }System.out.println(y);
    }
}
  • Why do you start with i = 2? Why not change it to i = 1? – Tag Dec 7 '13 at 6:01
  • @Tag I suppose that's mainly because the smallest prime number, according to primality as defined by modern mathematicians, is 2. – яүυк Nov 8 '16 at 6:40
  • @Dex'ter If a user enters 1 as the input then 1 is repeated multiple times in the output. This is, of course, still technically correct. By modifying the loop to start at 1 and removing the last 4 characters from the end of the Divisors string we end up with cleaner output. In hindsight, I was being pedantic. – Tag Nov 9 '16 at 20:49
up vote 18 down vote accepted

This code could do with some editing...

First of all is the spacing. It is absolutely horrible (we will fix that after the edits).

Also, the naming is horrible. Scanner x could be scanner and y could be num. As for z, it is completely unnecessary:

for (i = 2; i < y; i++) {
    long z = y % i;
    if (z != 0)
        continue;
    System.out.print(i + " , ");
}

Becomes:

for (i = 2; i < y; i++) {
    if (y % i != 0)
        continue;
    System.out.print(i + " , ");
}

The program can do without the continue statement:

for (i = 2; i < y; i++) {
    if (y % i == 0)
        System.out.print(i + " , ");
}

It's also a good idea to put braces around statements in an if statement, even when there is only one:

for (i = 2; i < y; i++) {
    if (y % i == 0) {
        System.out.print(i + " , ");
    }
}

You are also wasting time going through for loops doing nothing. After all, num's largest factor before itself possible is num / 2, which makes it more efficient doing it like this:

for (i = 2; i <= num / 2; i++) {
    if (num % i == 0) {
        System.out.print(i + " , ");
    }
}

I also noticed:

 public static void main(String args[])

It is better to put [] at the type (String):

public static void main(String[] args)

But the main problem is that you have a memory leak. It could be solved by closing the Scanner:

scanner.close();

Final code:

Your final code will look like this:

public class PrimeNum2 {
    public static void main(String args[]) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter the number :  ");
        long num = scanner.nextInt(), i;
        System.out.print("Divisors of " + num + " = 1 , ");
        for (i = 2; i <= num / 2; i++) {
            if (num % i == 0) {
                System.out.print(i + " , ");
            }
        }
        System.out.println(num);
        scanner.close();
    }
}
  • Condition in for loop should be i <=num/2 and not i <num/2. Test with num = 6. With above code: divisors of 6 will print 1, 2, 6 as loop starts from 2 and not check 3 – prashantsunkari Jan 20 '16 at 4:00
  • @prashantsunkari Good catch, will fix. – TheCoffeeCup Jan 20 '16 at 18:25
  • The only problem wiil be the special case of the number 1. Will print 'Divisors of 1 = 1 , 1'. – Musma Dec 6 '16 at 0:37
  • i should be local to the for loop. – Roland Illig Jul 29 '17 at 10:44

You can actually stop checking at Math.sqrt(num) because the current divisor always yields its conjugate:

for (i = 2; i <= Math.sqrt(num); i++) {
    if (num % i == 0) {
        System.out.print(i + " , ");
        if (i != num/i) {
            System.out.print(num/i + " , ");
        }
    }
}

We have to add an extra check, however, to avoid duplicate output in the case where num is a perfect square.

  • Math.sqrt is an expensive operation. You should not call that function more often than necessary. – Roland Illig Jul 29 '17 at 10:45
for( i=2; i <= (y / 2); i++)
{
    long z=y%i;
    if(z!=0)continue;
    System.out.print(i+" , ");
}

This for loop can be shortened, since a number's largest divisor (other than itself) will always be \$\frac{1}{2}\$. So instead of i < y, you could do i <= (y/2), assuming you are only counting integers, which you are since you say divisors.

\$136\$: largest divisor - \$68\$ (\$\le \frac{1}{2}\$ of \$136\$)

\$99\$: largest divisor - \$33\$ (\$\le \frac{1}{2}\$ of \$99\$)

As far as efficiency is concerned you should first generate a list of divisors 12-> {2,2,3} then group them -> {{2,2},{3}} then apply product of sets (see here).

This way you never check for divisors above n^(0.5) and make your search for divisors very efficient.

protected by Jamal Jul 29 '17 at 17:04

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.