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");
 }
}

• Adarsh: You wrote what code ?!
• user22048: Could you please describe what you mean by 'short'? Length of code? How fast it runs?
• user3070800: What i mean by short is , the length of the code ? :)

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.");
}

• Jesper: @user3070800 It's very easy to see that for yourself. If a number has one or more divisors, then at least one of them must be less than or equal to the square root of the number.
• Kyle: @EdgarBoda Yes, but you will find out it's divisible by 2 first, so you don't need to bother checking for divisibility by 5. Consider an integer N and a factor x. Since x is a factor of N, then N / x is also a factor of N. If x <= sqrt(N), then 1 <= sqrt(N) / x, then 1 / sqrt(N) <= 1 / x, then N / sqrt(N) <= N / x, then sqrt(N) <= N / x. Therefore any factor of N that's greater than or equal to sqrt(N) has a corresponding factor that's less than or equal to sqrt(N).
• 200_success: Rather than System.exit(), you could just return. It's more polite, and shorter too.
• Aseem Bansal: BTW using the sqrt in the condition check is very inefficient. Instead use for (long i = 2, n = Math.sqrt(x.nextLong()); i < n; i++) and it would be much better. Otherwise the square root will be evaluated every time.
• Peter Lawrey: This won't work for squares of primes e.g. 9 will fail to detect it is not prime.

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....

• 200_success: OP wanted to optimize for compactness, not efficiency.
• amon: Actually, long limit = (long)Math.sqrt(target) can fail in this context. Consider a very large prime p so that target = p*p, and that p can't be represented exactly as a floating point number. If the prime p is chosen suitably, then limit < p, in which case we get a false positive, because no factor is ever found. The solution would be to do something like limit = (long) nextHighestFloatingPointNumber(Math.sqrt(target)), but I have no idea how to implement this.
• amon: Hmm, I played around with a list of primes but they are to small to trigger inaccuracies in doubles, so my previous comment is just floating point paranoia.
• rolfl: @amon - since the input is a long (target is long) which is implicitly up-cast to double... how can the input to sqrt be to large?
• amon: Floating point numbers cannot represent all integers. Two "consecutive" floats can have a distance greater than 1. The idea of my comment was to find inputs where this distance creates false positives, which can occur if (a) target is rounded down to the nearest double during the implicit conversion, and (b) the sqrt of the two neighbouring doubles is different. I have not yet done a complete analysis to prove the existence or absence of such a value.

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++)

• user3070800: Is there a theorem which says that the max possible divider of a number is less than or equal to the square root of the number?
• Andrei Nicusan: No, there's no such theorem. But if there is such a number (let's call it x), the other factor y (that would make for x * y = the initial number) would be less than the square root, so one would have already found it and inferred the number is not prime. E.g. The square root of 64 is 8. 16 is a divider of 64 and it is larger than sqrt(64), but you would have already found 4 as a divider of 64 before reaching sqrt(64). And 4 * 16 = 64.
• user987339: 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. After this procedure only primes are left in the list.
• Peter Lawrey: Using i<Math.sqrt(y) will fail for squares of a prime number e.g. 9, 25, 49, ... will fail.
• user987339: Thanx for improving the answer.