Determining whether or not a number is prime

Question

I wrote this code in Java without using any methods, just by using simple for loop and if statements.

When we input a number, it checks whether it's a prime or not. If it's a prime, then it prints "It's a prime". And if it's not a prime number, it says "It's not a prime" and prints the first number which divides it.

For example, if we input 1457, it will output "1457 is not a prime 1457 Divide by 31".

I want to know whether or not I can make this coding shorter.

import java.util.*;
public class PrimeNum{
public static void main(String args[]){
       Scanner x=new Scanner(System.in);
       System.out.println("Enter the number :  ");
       long y=x.nextLong();
       long i;
       for( i=2;i<y;i++){
       long z=y%i;
           if(z==0){
           System.out.println(y+" is not a prime");
           System.out.println(y+" Divide by "+i);
           i=y;    
                         }

           }if(i==y) System.out.println("Number is prime"); 
            if(y==1) System.out.println("Number 1 is not a prime");
     }
}

Answer 1

You don't have to iterate from 2 to y.

It's enough to iterate from 2 to sqrt(y).

This is not necessarily a Java optimization, it's an optimization of the algorithm applicable no matter the implementation.

LATER EDIT

And this is how you can shorten your method:

public static void main(String args[]){
   Scanner x=new Scanner(System.in);
   System.out.println("Enter the number:");
   long y = x.nextLong();
   for(long i=2;i<=Math.sqrt(y);i++){
       if(y % i == 0){
           System.out.println(y+" is not a prime");
           System.out.println(y+" divides by "+i);
           System.exit();
       }

   }
   System.out.println(y + " is a prime number.");
}

Answer 2

Since this has been migrated to CodeReview, it makes sense to inspect it from a review perspective.

Others have correctly pointed out that the limit of your iteration is the root of the the number. That will impact the performance.... but what about your actual question: can the code be shorter (rather than faster)?

First, some comments....

1. you really should not use System.exit(...). A simple return would work better in this situation
2. You are not closing the Scanner when you are done with it. I know that in this case, working on System.in you don't think it's necessary, but, you should get in the habit of doing it. I have seen too many occasions where unclosed-handles create problems.
3. the variable names are horrible .... x, y and i? (Well, i is OK....).
4. in the current version of the code, you are still doing i++ and not i+=2. This is because you are starting at 2. If you start at 3 you can do a clean +=2.
5. Math.sqrt(...) returns a double. Doing a comparison against double for each loop is something the JIT compiler may be able to optimize, but I would err on the side of caution, and manually cast it outside the loop.

So, putting it together, I would suggest something like:

public static void main(String args[]){
    System.out.println("Enter the number:");
    try (Scanner scanner=new Scanner(System.in)) {
        final long target = scanner.nextLong();
        final long limit = (long)Math.sqrt(target);
        for(long factor = 2; factor <= limit; factor += factor == 2 ? 1 : 2){
            if(target % factor == 0) {
                System.out.printf("%d is not a prime\n%d divides by %d", target, target, factor);
                return;
            }

        }
        System.out.println(target + " is a prime number.");
    }
}

The above code is reasonably well structured, etc.

If I was aiming for raw performance though, and I threw out some of the validation rules, and allowed myself to hack it a bit, I would consider:

private static final long factor(final long target) {
    if (target <= 2) {
        return 1; // 1 and 2 are 'prime' external call will have to special-case 1 and negative numbers..
    }
    if ((target & 0x001) == 0) {
        return 2; // it's even.
    }
    final long limit = (long)Math.sqrt(target);
    for(long factor = 3; factor <= limit; factor += 2){
        if(target % factor == 0) {
            return factor;
        }
    }
    return 1;
}

public static void main(String args[]){
    System.out.println("Enter the number:");
    try (Scanner scanner=new Scanner(System.in)) {
        final long target = scanner.nextLong();
        final long fac = factor(target);
        if(fac > 1) {
            System.out.printf("%d is not a prime\n%d divides by %d", target, target, fac);
            return;
        }
        System.out.println(target + " is a prime number.");
    }
}

The reason for this is:

1. measuring performance with a single call is never going to do anything in Java - you need to call the code enough times to allow the JIT compiler to compile it.
2. It is unlikely that the JIT compiler will ever compile the main method
3. So I extract the 'hard' logic in to a seperate method that the JIT system can compile and isolate.
4. I handle the special cases seperately....
5. put the user-dialog outside the calculation....

Answer 3

The most efficient way to find all small primes was proposed by the Greek mathematician Eratosthenes. His idea was to make a list of positive integers not greater than n and sequentially strike out the multiples of primes less than or equal to the square root of n.

You can make less checks since the max possible divider is square root of the number. So you can change your for loop to:

for( i=2;i<=Math.sqrt(y);i++)