Wednesday, May 18, 2022

How to Check if Given Number is Prime in Java - With Example

Hello guys, today, we are going to discuss one of the most common programming exercises for beginners is, write a program to check if a given number is prime or not? There are many ways to check if a number is prime or not, but the most common of them is the trial division, which is what we will see in this tutorial. In my opinion, these kinds of programs are their first steps towards algorithmic understanding. You first come up with a solution, which is driven by the fact that prime numbers are natural numbers, that are not divisible by any positive number other than 1 and themselves. Then, you write a for loop to check every number, starting from 1 to a given number, to see if the given number is divisible by any positive number or not. This leads you to the solution.

Then you find some more the fact that there is no need to check till N-1, where N is the number we are checking for primeness, and checking till the square root of N is enough. This reduces a lot of time, especially while checking a large number is prime or not.

Further, you come to know that if it's not divisible by 2, then there is no need to checking for any other even number, and you increment the counter by 2 instead of 1. So in a way, you learn how to optimize your solution by taking advantage of the facts available.

After this, you can try something like the Fibonacci series or maybe finding factorial of a number in Java to do some more practice on programming. This will not only teach you language basics like loops, control statements like if-else, use of arithmetic, and relational operator but also helps to develop programming logic.

By the way, you can even take this problem of checking if a number is prime or not, to the next level, by trying to implement different algorithms for finding primes like the sieve of Atkin or sieve of Eratosthenes. In fact, in programming challenges, you often need to build your prime number cache up to a specific number to progress further in finding a solution.

Btw, if you need to refresh your Data Structure and algorithm skills to solve those problems, then I highly recommend checking out Data Structures and Algorithms: Deep Dive Using Java course on Udemy. It's a hands-on course and covers all essential data structures. It's also very affordable, and you can get in just $10 on Udemy flash sales, which happen every now and then.




How to Find if a Given Integer Number is a Prime Number or Not?

Now, we'll understand our Java program to see if a given integer number is prime or not. As I said, a number is called a prime number if it's only divisible by 1 or itself, which means the prime number doesn't have any positive divisor other than itself. There are many ways to check if the number is prime or not or generating a list of primes.

The most straightforward of them is known as trial division, which is a natural way of finding prime. In the trial division, you divide. It consists of testing whether n is a multiple of any integer between 2 and sqrt{n}.

In this program, I have presented three solutions or methods to check if the number is prime. The first solution is the implementation of the trial division, where we are checking from 2 to sqrt(n); we are using java.lang.Math class for calculating the square root.

Since this function returns double, we need to cast the result back into an integer. Our second method of checking if a number is prime or not is a little bit optimized than this as it doesn't check division by even numbers other than two.   The third method is most optimized for all three methods of prime number checking.

Btw, if you are also preparing for coding interviews or improving your algorithmic skill then I suggest you take a look at this wonderful course from Educative, Grokking the Coding Interview: Patterns for Coding Questions.

This is one of its kind courses that will not just teach you to solve the problem but also the pattern behind them, which means you can remember those patterns and apply them to many problems. A great way to build your coding and problem-solving skills.

How to check if Given number is prime in Java




Prime Number Checker in Java

And, here is the complete Java program to check if a given number is prime or not. This question is also asked on written tests and interviews as to how to print prime numbers from 1 to 100  or finding the prime factor of a number in Java.  And,  there is another exercise for you to do after this is checking if a number is Armstrong's number or not.


import java.util.Scanner;
/**
 * Java Program to check if a number is Prime or Not. This program accepts a
 * number from command prompt and check if it is prime or not. 
 *
 * @author  http://java67.blogspot.com
 */
public class PrimeTester {

    public static void main(String args[]) {
        Scanner scnr = new Scanner(System.in);
        int number = Integer.MAX_VALUE;
        System.out.println("Enter number to check if prime or not ");
        while (number != 0) {
            number = scnr.nextInt();
            System.out.printf("Does %d is prime? %s %s  %s %n", number,
                    isPrime(number), isPrimeOrNot(number), isPrimeNumber(number));
        }
    }


    /*
     * Java method to check if an integer number is prime or not.
     * @return true if number is prime, else false
     */
    public static boolean isPrime(int number) {
        int sqrt = (int) Math.sqrt(number) + 1;
        for (int i = 2; i < sqrt; i++) {
            if (number % i == 0) {
                // number is perfectly divisible - no prime
                return false;
            }
        }
        return true;
    }


    /*
     * Second version of isPrimeNumber method, with improvement like not
     * checking for division by even number, if its not divisible by 2.
     */
    public static boolean isPrimeNumber(int number) {
        if (number == 2 || number == 3) {
            return true;
        }
        if (number % 2 == 0) {
            return false;
        }
        int sqrt = (int) Math.sqrt(number) + 1;
        for (int i = 3; i < sqrt; i += 2) {
            if (number % i == 0) {
                return false;
            }
        }
        return true;
    }


    /*
     * Third way to check if a number is prime or not.
     */
    public static String isPrimeOrNot(int num) {
        if (num < 0) {
            return "not valid";
        }
        if (num == 0 || num == 1) {
            return "not prime";
        }
        if (num == 2 || num == 3) {
            return "prime number";
        }
        if ((num * num - 1) % 24 == 0) {
            return "prime";
        } else {
            return "not prime";
        }
    }
}

Output
Enter number to check if prime or not
2? Does 2 is prime? true prime number  true
3? Does 3 is prime? true prime number  true
4? Does 4 is prime? false not prime  false
5? Does 5 is prime? true prime  true
6? Does 6 is prime? false not prime  false
7? Does 7 is prime? true prime  true
17? Does 17 is prime? true prime  true
21? Does 21 is prime? false not prime  false
131? Does 131 is prime? true prime  true
139? Does 139 is prime? true prime  true


That's all in this program about how to check if a number is prime or not. The number must be an integer, as the concept of prime is only for natural numbers and not for floating-point numbers. As I said, there are a couple of more algorithms for checking if a number is prime or not, and some of the algorithms are optimized for finding prime numbers.

It is imperative for every programmer to know at least one fast way of finding a prime number, as this trial division is not fast enough for real-world problems. I suggest exploring the sieve of Atkin and the sieve of Eratosthenes's way of finding prime numbers.


Other Coding Problems for Practice

  • How to print the Pyramid pattern in Java? (solution)
  • How to reverse an int variable in Java? (solution)
  • 100+ Data Structure and Algorithms Problems (solved)
  • 10 Books to learn Data Structure and Algorithms (books)
  • Write a program to print the highest frequency word from a text file? (solution)
  • How to remove duplicate elements from ArrayList in Java? (solution)
  • How to solve the FizzBuzz problem in Java? (solution)
  • How to calculate factorial using recursion and iteration? (solution)
  • 10 Free Courses to learn Data Structure and Algorithms (courses)
  • How to find duplicate characters from String in Java? (solution)
  • How to find if given String is a palindrome in Java? (solution)
  • How to find a missing number in a sorted array? (solution)
  • How do you reverse the word of a sentence in Java? (solution)
  • How do you swap two integers without using a temporary variable? (solution)
  • Write a program to check if a number is the power of two or not? (solution)
  • How to check if a year is a leap year in Java? (answer)
  • Write code to implement the Bubble sort algorithm in Java? (code)
  • Write code to implement the Quicksort algorithm in Java? (algorithm)
  • How to reverse String in Java without using StringBuffer? (solution)
  • Write a program to code insertion sort algorithm in Java (program)
  • Top 10 Programming problems from Java Interviews? (article)

Thanks for reading this article so far. If you like this coding interview question, then please share it with your friends and colleagues. If you have any doubts or feedback, then please drop a note. 

P. S. - If you are looking for some free data structure and algorithms courses to improve your understanding of Data Structure and Algorithms, then you should also check the Data Structure in Java free course on Udemy. It's completely free, and all you need to do is create a free Udemy account to enroll in this course.

45 comments:

  1. Your isPrimeOrNot() method is not a correct way to detemine if a number is prime. (num * num - 1 ) % 24 == 0 is a property that is true for all primes but it can be true for some non primes as well eg num = 25.

    Also I think the code would clearer if you didn't add one to sqrt but instead used i <= sqrt in your for() loop.

    ReplyDelete
    Replies
    1. int sqrt = (int) Math.sqrt(number) + 1;
      for (int i = 3; i < sqrt; i += 2) {
      if (number % i == 0) { return false;
      }
      }


      This is a flawed approach. It counts 15 as a prime, where 5 is not (15 % 3 = 0).

      Delete
    2. I think you have implemented wrongly. how come 15 will be prime as per the code.
      for 15 as a number,
      int sqrt = (int) Math.sqrt(number) + 1; // sqrt = 4;
      loop will run only once as i < 4
      for (int i = 3; i < sqrt; i += 2) {
      then 15 % 3 == 0, so it return false. False mean its not a Prime number.

      Try same thing with 5 also.
      sqrt value of 5 will 3 i.e. (int) Math.sqrt(number) + 1;
      so the condition(i < sqrt) of for loop(3 < 3) is false so it won't get into and hence 5 is a Prime number.

      Delete
  2. The code is not valid to check the number is prime or not, which is written in the method isPrimeOrNot(int num).
    This method will also print some non-prime number like: 25,35,49...

    ReplyDelete
    Replies
    1. You are correct the code has bug, it prints 25 has prime number.

      Delete
  3. Check this out.
    I think its the best way to do without any errors or bugs.
    beginners may also like it as it lucid and easy.

    int limit = 100;

    System.out.println("Prime numbers between 1 and " + limit);

    //loop through the numbers one by one
    for(int i=1; i < 100; i++){

    boolean isPrime = true;

    //check to see if the number is prime
    for(int j=2; j < i ; j++){

    if(i % j == 0){
    isPrime = false;
    break;
    }
    }
    // print the number
    if(isPrime)
    System.out.print(i + " ");
    }



    Ashim Kumar Halder
    Android Developer
    ashimkr.halder@gmail.com

    ReplyDelete
  4. You should add line if(number < 2) return false; to method isPrimeNumber

    ReplyDelete
    Replies
    1. Hi, actually if(number %2==0) will also check number<2 condition.
      1%2 equals 0 or -4%2 equals 0.

      Delete
  5. public static boolean isPrime(int number){
    if(number%2==0){
    return false;
    }
    for(int i=3;i<number;i=i+2){
    if(number%i==0){
    return false;
    }
    }
    return true;
    }

    ReplyDelete
  6. hi I hope this works


    import java.util.Scanner;

    public class Prime {
    public static void main(String[] args) {
    Prime p= new Prime();
    Scanner sc= new Scanner(System.in);
    System.out.println("Enter the number to check its prime or not: ");
    int num=sc.nextInt();
    System.out.println(p.primenum(num));
    }
    private boolean primenum(int num)
    {
    boolean isprime=true;
    if(num==2||num==3)
    {
    return isprime;
    }
    if(num%2==0)
    {
    return isprime=false;
    }
    for(int i=3;i<num;i+=2)
    {
    if(num%i==0)
    {
    return isprime=false;
    }
    }
    return isprime;

    }

    }

    ReplyDelete
  7. Hi, this program checks if a number (+ve integer) entered is prime or not. It prompts the user to enter a +ve integer, checks it and displays if it's a prime number or not.

    Try and run the program. If there is any question or comment on the program, please drop it here. Thanks
    ..............................................................................

    import java.util.Scanner ;

    public class PrimeNumbers
    {
    public static void main(String[] args)
    {
    Scanner input = new Scanner(System.in) ;

    int counter = 1;

    System.out.printf(" \n Please enter a +ve Integer :") ;
    int num = input.nextInt() ;

    if (num == 1 || num % num == 0)
    {
    ++counter ;

    if (num == 1)
    {
    --counter ;
    }
    }

    for (int i = 2; i <= num; i++)
    {
    if (( num == i ) ^ (num % i == 0))
    {
    counter ++;
    }
    }

    if ( counter == 2)
    {
    System.out.printf("\n %d is a prime number", num) ;
    }
    else
    {
    System.out.printf("\n %d is not a prime number", num) ;
    }
    }
    }

    ReplyDelete
    Replies
    1. Can you explain the logic? Why you are checking counter and what is the use of bitwise ^ operator here?

      Delete
  8. import java.util.Scanner ;

    public class PrimeNumbers
    {
    public static void main(String[] args)
    {
    int i,count=1;
    Scanner input = new Scanner(System.in) ;
    System.out.printf(" \n Please enter an Integer :") ;
    int num = input.nextInt() ;
    for(i=2;i0)
    {
    System.out.printf("\n %d is a prime number", num) ;
    }
    else
    {
    System.out.printf("\n %d is not a prime number", num) ;
    }
    }
    }

    ReplyDelete
    Replies
    1. import java.util.Scanner ;

      public class PrimeNumbers
      {
      public static void main(String[] args)
      {
      int i,count=1;
      Scanner input = new Scanner(System.in) ;
      System.out.printf(" \n Please enter an +op Integer :") ;
      int num = input.nextInt() ;
      for(i=2;i0)
      {
      System.out.printf("\n %d is a prime number", num) ;
      }
      else
      {
      System.out.printf("\n %d is not a prime number", num) ;
      }
      }
      }

      Delete
    2. import java.util.Scanner;
      public class Main{

      public static void main(String []args)
      {
      int a;
      boolean flag=false;
      System.out.println("enter number:");
      Scanner sc=new Scanner(System.in);
      a=sc.nextInt();
      for(int i=2;i<=a/2;i++)
      {
      if(a%i==0)
      {
      flag=true;
      break;
      }
      }
      if(!flag)
      System.out.println("is prime");
      else
      System.out.println("is not prime");
      }


      }

      Delete
  9. This comment has been removed by the author.

    ReplyDelete
  10. public static boolean isPrime(int num) {
    boolean isPrime = true;
    for(int i = 2 ; i <=num/2; i++) {
    if(num%i==0) {
    isPrime = false;
    break;
    }
    }
    return isPrime;
    }

    ReplyDelete
  11. public class PrimeExample{
    public static void main(String args[]){
    int i,m=0,flag=0;
    int n=3;//it is the number to be checked
    m=n/2;
    if(n==0||n==1){
    System.out.println(n+" is not prime number");
    }else{
    for(i=2;i<=m;i++){
    if(n%i==0){
    System.out.println(n+" is not prime number");
    flag=1;
    break;
    }
    }
    if(flag==0) { System.out.println(n+" is prime number"); }
    }//end of else
    }
    }

    ReplyDelete
    Replies
    1. public class PrimeExample2{
      static void checkPrime(int n){
      int i,m=0,flag=0;
      m=n/2;
      if(n==0||n==1){
      System.out.println(n+" is not prime number");
      }else{
      for(i=2;i<=m;i++){
      if(n%i==0){
      System.out.println(n+" is not prime number");
      flag=1;
      break;
      }
      }
      if(flag==0) { System.out.println(n+" is prime number"); }
      }//end of else
      }
      public static void main(String args[]){
      checkPrime(1);
      checkPrime(3);
      checkPrime(17);
      checkPrime(20);
      checkPrime(53);
      checkPrime(1289);
      checkPrime(2017);
      checkPrime(6933);
      }
      }

      Delete
  12. public class PrimeExample{
    public static void main(String args[]){
    int i,m=0,flag=0;
    int n=3;//it is the number to be checked
    m=n/2;
    if(n==0||n==1){
    System.out.println(n+" is not prime number");
    }else{
    for(i=2;i<=m;i++){
    if(n%i==0){
    System.out.println(n+" is not prime number");
    flag=1;
    break;
    }
    }
    if(flag==0) { System.out.println(n+" is prime number"); }
    }//end of else
    }
    }

    ReplyDelete
  13. public class CheckPrimeNumber {

    public static void main(String[] args) {

    int temp;
    boolean isPrime= true;
    Scanner s = new Scanner(System.in);
    int number = Integer.MAX_VALUE;
    System.out.println("Enter a number to check prime:");
    number = s.nextInt();
    s.close();

    for(int i=2;i<=number/2;i++)
    {
    temp= number%i;
    if(temp==0)
    {
    isPrime = false;
    break;
    }
    }
    if(isPrime)
    System.out.println(number+"is a prime number");
    else
    System.out.println(number+"is not a prime number");

    }

    }

    ReplyDelete
  14. why are we adding 1 to sqrt of number?

    ReplyDelete
  15. import java.util.*;
    import java.io.*;
    import java.math.*;

    class Prime
    {
    public static void main(String args[])
    {
    Scanner sc=new Scanner(System.in);
    int i,n,j,k=0;

    System.out.println("Enter any Number:");
    n=sc.nextInt();

    j=(int)Math.sqrt(n);

    for(i=2;i<=j;i++)
    {
    if(n%i==0)
    {
    k++;
    }
    else
    ;
    }
    if(k==0)
    System.out.println("Prime Number");
    else
    System.out.println("Not a Prime Number");
    }
    }

    ReplyDelete
  16. hi,
    please verify whether it is correct:

    public class task {

    public static void main(String[] args) {
    int a=238;
    if(((a%2==0)||(a%3==0))&&((a!=2)||(a!=3))) {
    System.out.print("given num is not prime");
    }
    else {
    System.out.print("given num is prime");
    }
    }

    }

    ReplyDelete
  17. please verify whether it is valid:

    public class task {

    public static void main(String[] args) {
    int a=238;
    if(((a%2==0)||(a%3==0))&&((a!=2)||(a!=3))) {
    System.out.print("given num is not prime");
    }
    else {
    System.out.print("given num is prime");
    }
    }

    }

    ReplyDelete

  18. public class Test {

    public static void main(String[] args) {
    int number = 111;
    for(int i=2;i<Math.sqrt(number);i++) {
    if(number%i==0) {
    System.out.println("nt prime number" + i);
    return;
    }
    }
    System.out.println(" prime");
    }
    }

    ReplyDelete
  19. int sqrt = (int) Math.sqrt(number) + 1;
    for (int i = 3; i < sqrt; i += 2) {
    if (number % i == 0) {
    return false;
    }
    }

    This is flawed. 15 returns as prime. 15 % 3 is 0. I made an if statement, that could be implemented as a switch, that checks the number if it is divisible by the first 4 natural prime numbers (2, 3, 5, 7).

    ReplyDelete
  20. Well 15697 is not prime but if ((num * num - 1) % 24 == 0) will be true for it.

    ReplyDelete
  21. int num = 131;
    if(!((num%2==0)||(num%3==0)||(num%5==0)||(num%7==0)||(num%10==0))) {
    System.out.println("num \""+ num +"\" is prime");
    }else {
    System.out.println("num \""+ num +"\" is NOT prime");
    }

    is this a valid approach?

    ReplyDelete
  22. import java.util.Scanner;


    public class PrimeNumber {

    /**
    * @param args
    */
    public static void main(String[] args) {
    int count = 0;
    System.out.println("Enter a number");
    int n=new Scanner(System.in).nextInt();
    for(int i=1;i<=n;i++){
    if(n%i==0){
    count++;
    }
    }
    if(count==2){
    System.out.println(n+"is a Prime number");
    }
    else{
    System.out.println(n+"Not a Prime number");
    }

    }

    }

    ReplyDelete
  23. Simple Way....

    int a= 5;

    int div=2;

    While(a>div)
    {
    if(a%div==0){
    break;
    }div++;
    }
    if(a==div)
    System.out.print("Prime Number");
    else
    System.out.print("Not Prime Number");

    ReplyDelete
  24. Hey here is a logic!

    class Emmanuel{
    public static void main(String [] args){
    for(int i = 2; i<=50; i++){
    for (int j = 2; j<=i; j++){
    if(j==i)

    System.out.println(i);
    }

    if (i%j==0){
    break;
    }
    }
    }
    }
    }

    ReplyDelete
  25. Hi friends every one is doing a great job on whether the number is prime or not.
    But I have two question is following in the below
    Print prime numbers between given intervals/numbers?
    Or
    Print Prime numbers from given number
    (Like if you enter 5 then print prime numbers after 5 only)

    ReplyDelete
    Replies
    1. import java.util.Scanner;
      class PrintPrime
      {
      public static void main(String[] args) {
      Scanner s=new Scanner(System.in);
      System.out.println("Enter the number upto print");
      int num=s.nextInt();
      System.out.println("prime number from");
      int from=s.nextInt();
      System.out.println("the prime number series is: ");
      for (int i=from;i<=num;i++ ) {
      int count=0;
      for (int j=1;j<=i ;j++) {
      if(i%j==0)
      {
      count++;
      }
      }
      if(count==2)
      {
      System.out.print(i+" ");
      }
      }
      }
      }

      Delete
  26. import java.util.Scanner;
    class IsPrime
    {
    public static void main(String[] args) {
    Scanner s=new Scanner(System.in);
    System.out.println("Enter the number checked prime or not");
    int num=s.nextInt();
    if(num==0||num==1)
    {
    System.out.println("not a prime number");
    }
    else
    {int count=0;
    for (int i=2;i<=num ;i++ ) {
    if (num%i==0) {
    count++;
    }
    }
    if(count==1)
    {
    System.out.println(num+" is a prime number");
    }
    else{
    System.out.println(num+" is not a prime number");
    }
    }
    }
    }

    ReplyDelete
  27. public class PrimeNumber {

    public static boolean prime(int n) {
    boolean isPrime = true;

    for(int i = 2; i<n;i++) { //prime numbers can be divided by 1 and itself.
    isPrime = (n%i==0)&&(n!=2)&&(n!=1)? false:true;
    if(isPrime == false) break; //if isPrime is false, it is not a prime number, therefore the loop should not continue
    }
    return isPrime;
    }

    public static void main(String[] args) {

    Scanner in = new Scanner(System.in);
    System.out.print("Enter a number: "); //user input
    int n = in.nextInt();

    String output= (prime(n) == true)? " is a prime number":" is NOT a prime number"; //output condition.
    System.out.println(n+output);
    in.close();

    }
    }

    ReplyDelete
  28. The third way to checks seems to be wrong. It shows numbers like 25, 35, 49, 55, 65, 77, 85, 91, 95, 115, 119, 121, 125, 133, 143, 145, 155, 161, 169, 175, 185, 187 etc. as prime.

    ReplyDelete
    Replies
    1. Yes, you are correct, it seems something is wrong with the logic, I will take a look. thx for pointing it out.

      Delete
  29. private static boolean isPrime(int num) {
    boolean isprime=false;
    if(num/num==1 && num%2!=0) {
    if(num%3!=0) {
    isprime=true;
    }
    }
    return isprime||num==2||num==3;

    }

    ReplyDelete

  30. import java.util.Scanner;

    public class Prime {

    public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n;

    while (true) {
    System.out.println("Enter the number : ");
    n = sc.nextInt();
    int count=0;
    for(int i = 1 ; i<=n ; i++) {
    if (n % i == 0) {
    count++;
    }
    }
    if(count > 2) {
    System.out.println(n + " is not prime Number");
    } else {
    System.out.println(n + " is prime Number");
    }
    }

    }

    }


    ReplyDelete
  31. package com.InterviewQuestions;
    import java.util.Scanner;

    public class Prime
    {
    public static void main(String[] args)
    {
    Scanner sc = new Scanner(System.in);
    int count=0;
    System.out.println("Enter Number to check whether its Prime or Not");
    int number = sc.nextInt();

    if(number<=1)
    {
    System.out.println("Not a Prime Number");
    }


    for(int i=2;i<=number/2;i++)
    {
    if(number%i==0)
    {
    count++;
    }
    }

    if(count>=1)
    {
    System.out.println("Not a Prime Number");
    }
    else
    {
    System.out.println("Prime Number");
    }

    sc.close();
    }
    }

    ReplyDelete

Feel free to comment, ask questions if you have any doubt.