How to determine if a number is prime

Question

Okay my issue is less of how to figure out if a number is prime, because I think I figured that out, but more of how to get it to display properly.

Here's my code:

public static void main(String[] args) {
    // Declare Variables
    int randomNumbers = 0;
    int sum = 0;
    //Loop for number generation and print out numbers
    System.out.print("The five random numbers are: ");
    for (int i = 0; i <= 4; i++)
    {
        randomNumbers = (int)(Math.random()*20);
        sum += randomNumbers;

        if (i == 4) {
            System.out.println("and " + randomNumbers + ".");
        }
        else {
            System.out.print(randomNumbers + ", ");
        }
    }
    //Display Sum
    System.out.println("\nThe sum of these five numbers is " + sum + ".\n");

    //Determine if the sum is prime and display results
    for(int p = 2; p < sum; p++) {
        if(sum % p == 0)
            System.out.println("The sum is not a prime number.");
        else 
            System.out.println("The sum is a prime number.");
        break;
        }
    }


}

Now my problem is, if the number ends up being something like 9, it'll say it is a prime number, which it is not. I think the issue is that the break is stopping it after one loop so it's not incrementing variable p so it's only testing dividing by 2 (I think). But if I remove the break point it will print out "The sum is/is not a prime number" on every pass until it exits the loop. Not sure what to do here.

Answer 1

you can use the Java BigInteger class' isProbablePrime method to determine and print whether the sum is prime or not prime in an easy way.

 BigInteger number = new BigInteger(sum);
        if(number.isProbablePrime(1)){
            System.out.println("prime");
        }
        else{
            System.out.println("not prime");
        }

You can read more about this method here https://docs.oracle.com/javase/7/docs/api/java/math/BigInteger.html#isProbablePrime%28int%29

Answer 2

Small prime numbers

Use Apache Commons Math primality test, method is related to prime numbers in the range of int. You can find source code on GitHub.

<dependency>
    <groupId>org.apache.commons</groupId>
    <artifactId>commons-math3</artifactId>
    <version>3.6.1</version>
</dependency>

// org.apache.commons.math3.primes.Primes
Primes.isPrime(2147483629);

It uses the Miller-Rabin probabilistic test in such a way that a result is guaranteed: it uses the firsts prime numbers as successive base (see Handbook of applied cryptography by Menezes, table 4.1 / page 140).

Big prime numbers

If you are looking for primes larger than Integer.MAX_VALUE:

1. Use BigInteger#isProbablePrime(int certainty) to pre-verify the prime candidate

   Returns true if this BigInteger is probably prime, false if it's definitely composite. If certainty is ≤ 0, true is returned. Parameters: certainty - a measure of the uncertainty that the caller is willing to tolerate: if the call returns true the probability that this BigInteger is prime exceeds (1 - 1/2certainty). The execution time of this method is proportional to the value of this parameter.

2. Next use "AKS Primality Test" to check whether the candidate is indeed prime.

Answer 3

With most efficient time Complexity ie O(sqrt(n)) :

public static boolean isPrime(int num) {

    for (int i = 2; i * i <= num; i++) {
        if (num % i == 0) {
            return false;
        }
    }

    return true;
}

Answer 4

So many answers have been posted so far which are correct but none of them is optimized. That's why I thought to share the optimized code to determine prime number here with you. Please have a look at below code snippet...

private static boolean isPrime(int iNum) {
boolean bResult = true;
if (iNum <= 1 || iNum != 2 && iNum % 2 == 0) {
    bResult = false;
} else {
    int iSqrt = (int) Math.sqrt(iNum);
    for (int i = 3; i < iSqrt; i += 2) {
    if (iNum % i == 0) {
        bResult = false;
        break;
    }
    }
}
return bResult;
}

Benefits of above code-:

1. It'll work for negative numbers and 0 & 1 as well.
2. It'll run the for loop only for odd numbers.
3. It'll increment the for loop variable by 2 rather than 1.
4. It'll iterate the for loop only upto square root of number rather than upto number.

Explanation-:

I have mentioned the four points above which I'll explain one by one. Code must be appropriately written for the invalid inputs rather the only for valid input. Whatever answers have been written so far are restricted to valid range of input in which number iNum >=2.

We should be aware that only odd numbers can be prime, Note-: 2 is the only one even prime. So we must not run for loop for even numbers.

We must not run for loop for even values of it's variable i as we know that only even numbers can be devided by even number. I have already mentioned in the above point that only odd numbers can be prime except 2 as even. So no need to run code inside for loop for even values of variable i in for.

We should iterate for loop only upto square root of number rather than upto number. Few of the answers has implemented this point but still I thought to mention it here.

Answer 5

You are right, currently your code tests dividing by two, and the break command is stopping after one loop.

After the first go of your loop (p==2), the break will always stop the loop.

The fastest fix to your code will change the loop part like this:

boolean isPrime=true;
for(int p = 2; p < sum; p++) {
    if(sum % p == 0) {
        isPrime=false;
        System.out.println("The sum is not a prime number.");
        break;
    }
}
if (isPrime)
    System.out.println("The sum is a prime number."); 

This code can be improved for efficiency and for code elegance.

For efficiency, you don't need to check divisibility by all numbers smaller than sum, it's enough to check all numbers smaller by square-root of sum.

For better code, create a seperate function to test if a number is prime.

Here is an example that implements both.

 // tests if n is prime
 public static boolean isPrime(int n) {
     if (n<2) return false;
     for(int p = 2; p < Math.sqrt(n); p++) {
        if(n % p == 0) return false;  // enough to find one devisor to show n is not a prime
     }
     return true; // no factors smaller than sqrt(n) were found
 }

 public static void main(String []args){
    ...
    System.out.println("sum is "+ sum);
    if (isPrime(sum)) 
        System.out.println("The sum is a prime number.");
    else 
        System.out.println("The sum is not a prime number.");
 }

Answer 6

You need to store whether or not the number is prime in a boolean outside of the loop:

//Determine if the sum is prime and display results
boolean isPrime = true;
for(int p = 2; p < sum; p++) {
    if(sum % p == 0){
        isPrime = false;
        break;
    }
}
if(isPrime){
   System.out.println("The sum is a prime number.");
} else {
   System.out.println("The sum is not a prime number."); 
}

Answer 7

Your method for finding if your number is prime is the correct method. To make it so that it does not consistently print out whether or not the number is prime, you could have an external variable, which represents whether or not the number is prime.

Such as

    boolean prime = true;
    for (int p = 2; p < sum; p++) {
        if (sum % p == 0) {
            prime = false;
            break;
        }
    }
    if (prime)
        System.out.println("The sum is a prime number.");
    else
        System.out.println("The sum is not a prime number.");

By doing this method the program will assume the number is prime until it proves that wrong. So when it finds it is not prime it sets the variable to false and breaks out of the loop.

Then after the loop finishes you just have to print whether or not the number was prime.

A way that you could make this loop faster is to go from when p = 2 to when p = the square root of sum. So using this method your for loop will look like this:

    double sq = Math.sqrt((double)sum);
    for (int p = 2; p < sq; p++) {
        //Rest of code goes here
    }

Hope this helps