# Finding divisors of a number

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

import java.util.Scanner;

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. – Grajdeanu Alex. 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

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.