How does this prime number test in Java work?

Question

The code snippet below checks whether a given number is a prime number. Can someone explain to me why this works? This code was on a study guide given to us for a Java exam.

public static void main(String[] args)
{    
    int j = 2;
    int result = 0;
    int number = 0;
    Scanner reader = new Scanner(System.in);
    System.out.println("Please enter a number: ");
    number = reader.nextInt();
    while (j <= number / 2)
    {
        if (number % j == 0)
        {
           result = 1;
        }
        j++;
    }
    if (result == 1)
    {
        System.out.println("Number: " + number + " is Not Prime.");
    }
    else
    {
        System.out.println("Number: " + number + " is Prime. ");
    }
}

Excipient

Where you did'nt get ? – Stress

Whats the definition of a prime; a number divisible by only itself and 1 – Filibeg

What is the part that you dont understand? i need to know exactly what to explain.. – Hailey

Why would it not work? – Plinth

Why the - votes??? It's taking a number, dividing it by 2. Seeing if that number is greater than 2. Truncating that number. Taking the mod 2 of that number. If that mod is equal to 1, all it says about the number is that it's odd. I see nothing about primality. – Excipient

@AdamStaples Wow, you can't even read the code straight. "If that mod is equal to 1"? It checks whether the mod is equal to 0, i.e. j divides the number. – Dipsomania

You need to explain in the question body about what specifically you're having trouble understanding, the general algorithm for testing primality, or the specifics of this Java code used to implement it. If you look at the answers that you've gotten, a lot of them are just code dumps of (presumable) Java implementations of primality testing. These poor answers can be avoided if your question itself was clearer. – Dehumidifier

Answer 1

Overall theory

The condition if (number % j == 0) asks if number is exactly divisible by j

The definition of a prime is

a number divisible by only itself and 1

so if you test all numbers between 2 and number, and none of them are exactly divisible then it is a prime, otherwise it is not.

Of course you don't actually have to go all way to the number, because number cannot be exactly divisible by anything above half number.

Specific sections

While loop

This section runs through values of increasing j, if we pretend that number = 12 then it will run through j = 2,3,4,5,6

  int j = 2;
  .....
  while (j <= number / 2)
  {
      ........
      j++;
  }

If statement

This section sets result to 1, if at any point number is exactly divisible by j. result is never reset to 0 once it has been set to 1.

  ......
  if (number % j == 0)
  {
     result = 1;
  }
  .....

Further improvements

Of course you can improve that even more because you actually need go no higher than sqrt(number) but this snippet has decided not to do that; the reason you need go no higher is because if (for example) 40 is exactly divisible by 4 it is 4*10, you don't need to test for both 4 and 10. And of those pairs one will always be below sqrt(number).

It's also worth noting that they appear to have intended to use result as a boolean, but actually used integers 0 and 1 to represent true and false instead. This is not good practice.

Filibeg

Okay I understand that a number p is prime if and only if the only numbers that divide it are p and 1 themselves. In this example though the user enters a number, say, k. Then it tests whether or not k/2 is greater or equal to 2 (since we don't want to check 1 & 2. 2 being prime automatically and 1 being neither prime nor composite). Then it takes k mod (j = 2), Idk I'm just having a hard time following the code. I know about prime numbers and such, I've done a lot of number theory. I'm terrible at reading java code though I suppose. – Excipient

@AdamStaples Where are these variable names p and k coming from, unless we keep to the variable names in the question madness will ensue – Filibeg

I'm assuming k is number – Filibeg

@AdamStaples Perhaps it would help if you indicated which lines in your question are not clear – Filibeg

Okay I'm not understand why it's taking number mod j when j is only equal to 2. Should it take mod number to see if it's divisible by itself and 1? – Excipient

@AdamStaples j++; increases the value of j, the loop will test j at 2,3,4,5,6,.......number/2-1,number/2 – Filibeg

@AdamStaples I've added a section on what the while loop is doing – Filibeg

Oh I feel like an idiot now. Because it's a while loop, it'll iterate through all the choices until the Boolean for the while loop is 'true'. Since it only checks number/2 times, it'll never reach j = number and thus if prime will never be congruent to 0 mod j and thus nuver equal '1'. Okay Idk if I made any sense but I completely see why it works. Okay thanks! – Excipient

@AdamStaples Awesome, glad to help. Java is difficult to get into but really nice once you have – Filibeg

Answer 2

I've tried to comment each line to explain the processes going on, hope it helps!

int j = 2;   //variable
int result = 0; //variable
int number = 0; //variable
Scanner reader = new Scanner(System.in); //Scanner object
System.out.println("Please enter a number: "); //Instruction
number = reader.nextInt(); //Get the number entered
while (j <= number / 2) //start loop, during loop j will become each number between 2 and 
{                             //the entered number divided by 2
    if (number % j == 0) //If their is no remainder from your number divided by j...
    {
        result = 1;  //Then result is set to 1 as the number divides equally by another number, hergo
    }                //it is not a prime number
    j++;  //Increment j to the next number to test against the number you entered
}
if (result == 1)  //check the result from the loop
{
    System.out.println("Number: " + number + " is Not Prime."); //If result 1 then a prime   
}
else
{
    System.out.println("Number: " + number + " is Prime. "); //If result is not 1 it's not a prime
}    

Hysterogenic

This answer can be greatly improved if you also gave an explanation outside of the code, in plain English. – Dehumidifier

Answer 3

It works by iterating over all number between 2 and half of the number entered (since any number greater than the input/2 (but less than the input) would yield a fraction). If the number input divided by j yields a 0 remainder (if (number % j == 0)) then the number input is divisible by a number other than 1 or itself. In this case result is set to 1 and the number is not a prime number.

Disk

Answer 4

Java java.math.BigInteger class contains a method isProbablePrime(int certainty) to check the primality of a number.

isProbablePrime(int certainty): A method in BigInteger class to check if a given number is prime. For certainty = 1, it return true if BigInteger is prime and false if BigInteger is composite.

Miller–Rabin primality algorithm is used to check primality in this method.

import java.math.BigInteger;

public class TestPrime {

    public static void main(String[] args) {
        int number = 83;
        boolean isPrime = testPrime(number);
        System.out.println(number + " is prime : " + isPrime);

    }

    /**
     * method to test primality
     * @param number
     * @return boolean
     */
    private static boolean testPrime(int number) {
        BigInteger bValue = BigInteger.valueOf(number);

        /**
         * isProbablePrime method used to check primality. 
         * */
        boolean result = bValue.isProbablePrime(1);

        return result;
    }
}

Output: 83 is prime : true

For more information, see my blog.

Guest

Answer 5

Do try

public class PalindromePrime   {
     private static int g ,k ,n =0,i,m ; 

     static String b ="";
    private static Scanner scanner = new Scanner( System.in );

    public static void main(String [] args) throws IOException {

        System.out.print(" Please Inter Data : "); 
        g = scanner.nextInt();  

        System.out.print(" Please Inter Data 2  : "); 
        m = scanner.nextInt();

        count(g,m);


        }

//      
        //********************************************************************************    


    private static    int count(int L, int R) 

        for( i= L ; i<= R ;i++){
            int count = 0 ;
            for( n = i ; n >=1 ;n -- ){

                if(i%n==0){

                    count = count + 1 ;
                }           
            }
            if(count == 2)
            {       
                b = b +i + "" ; 
            }   

        }

        System.out.print("  Data  : "); 
        System.out.print("  Data : \n "  +b );  

        return R;

        }
} 

Sophey