17
\$\begingroup\$

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);
    }
}
\$\endgroup\$
  • \$\begingroup\$ Why do you start with i = 2? Why not change it to i = 1? \$\endgroup\$ – Tag Dec 7 '13 at 6:01
  • \$\begingroup\$ @Tag I suppose that's mainly because the smallest prime number, according to primality as defined by modern mathematicians, is 2. \$\endgroup\$ – Grajdeanu Alex. Nov 8 '16 at 6:40
  • \$\begingroup\$ @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. \$\endgroup\$ – Tag Nov 9 '16 at 20:49
19
\$\begingroup\$

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();
    }
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 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 \$\endgroup\$ – prashantsunkari Jan 20 '16 at 4:00
  • \$\begingroup\$ @prashantsunkari Good catch, will fix. \$\endgroup\$ – TheCoffeeCup Jan 20 '16 at 18:25
  • \$\begingroup\$ The only problem wiil be the special case of the number 1. Will print 'Divisors of 1 = 1 , 1'. \$\endgroup\$ – Musma Dec 6 '16 at 0:37
  • \$\begingroup\$ i should be local to the for loop. \$\endgroup\$ – Roland Illig Jul 29 '17 at 10:44
9
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Math.sqrt is an expensive operation. You should not call that function more often than necessary. \$\endgroup\$ – Roland Illig Jul 29 '17 at 10:45
6
\$\begingroup\$
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\$)

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$

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