Prime Number Program in Java

In this post, we will develop prime number program in Java, program to check the prime number in Java, and java program to print prime numbers between two numbers.

A natural number which has only two factors ( 1 and itself ) is called a prime number. For example- 5 is a prime number because it has only two factors 1 and 5. Similarly, 9 is not a prime number because it has more than 2 factors that are 1,3, and 9.

Simple Prime Number Program in Java

To develop a program to check the given number is a prime number or not in java; first, you should know how to develop a Java program to find out all factors of a number. Because if any number has more than 2 factors then only, it is a prime number. All negative numbers, 0 and 1 are not the prime numbers.

Prime number program in Java using for loop

import java.util.Scanner;

public class SimplePrimeNoProgram {

  public static boolean isPrime(int number){

    // All negative numbers, 0 and 1 
    // are not a prime number
    if(number<=1) return false;

    // check for remaining
    for(int i=2; i<number; i++)
        if(number%i == 0) 
            return false;

    return true;
  }

  public static void main(String[] args) {

    // declare variables
    int number = 0;
    boolean flag = false;

    // create Scanner class object
    Scanner scan = new Scanner(System.in);

    // read number
    System.out.print("Enter a number:: ");
    number = scan.nextInt();

    // check number is prime number or not
    flag  = isPrime(number);

    // display result
    if(flag) // true
       System.out.println(number+
                " is a prime number");
    else 
       System.out.println(number+
                " is not a prime number");

    // close Scanner class object
    scan.close();
  }
}

Output for different test cases:-

Enter a number:: 11
11 is a prime number

Enter a number:: 9
9 is not a prime number

The time complexity of this solution is O(n).

Also see:- Special number, Magic number, Armstrong number, Perfect number, Evil Number, Spy Number, Sunny number in Java

Using while loop

The previous prime number program in java was developed using for loop, but we can also use a while loop instead of the for loop. Use the below method in the previous program.

Prime number method in Java using while loop

public static boolean isPrime(int number) {

   // declare variables
   int i = 2;

   // negative numbers, 0 and 1 
   // are not a prime number
   if(number<=1) return false;

   // loop to repeat the process
   while(i<number) {
       if(number%i == 0) 
           return false;
       i++;
   }

   return true;
}

The time complexity of this solution is O(n).

Program to check prime number in Java

The above programs are right and give correct output but they give less performance, their time complexity was O(n). We can optimize the above programs.

There are some points we should keep in mind to develop the best prime program in java which will give high performance.

• All negative numbers, 0 and 1 are not the prime numbers.
• 2 is the only even prime number.
• Every prime number (except 2 and 3) can be presented in the form of 6n+1 or 6n-1
• 2 and 3 are the only two consecutive natural numbers which are prime too.

We can do following optimizations,

1) Instead of checking till i=1 to number, we should check only up to √n.

In the post find factors in java we learned that we can use the sqrt() method to limit the iteration, and divide the number by iterator variable to find the factors which are greater than the square root value of the number. The code can be written as,

for(….; i<=Math.sqrt(number); ….) {
      // logic
}

2) All prime numbers except 2 and 3 are the form of 6k ± 1. See:- Primality test

Since all integers can be expressed as (6k+i) for some integer k and for i=-1,0,1,2,3, or 4 (Here 5 is written as -1). Since the integers represented as 6k+0, 6k+2, and 6k+4 are even numbers and divisible by two so they can’t be a prime number. The integers represented as 6k+3 will be divisible by 3 so it also can’t be a prime number. Now, the remaining integers which are represented as 6k+1 and 6k-1 may be a prime number or composite number. So, we need to check only for numbers which are represented as 6k ± 1.

Hence, it is better to check number is divisible by 2 or 3, if yes then it is not a prime number.

if(number%2==0 || number%3==0) 
return false;

The logic for prime number

Java method code for checking the given number is a prime number or not

public static boolean isPrime(int number) {

  // negative numbers, 0 and 1 are 
  // not a prime number
  if( number <= 1 ) return false;

  // 2 and 3 are prime numbers
  if( number <= 3 ) return true;

  // numbers divisible by 2 and 3
  // are not prime number
  if(number%2==0 || number%3==0)
      return false;

  // logic for remaining numbers
  for(int i=5; i<=Math.sqrt(number); i=i+6) {

      // 6k+1 => number%i
      // 6k-1 => number % (i+2)
      if(number%i == 0 || number%(i+2) == 0) 
          return false;
  }

  // if all above conditions are not satisfied
  return true;
}

The time complexity for this method is O(√n).

Java Program

In the checkPrime() method we used for loop to check prime number in java but we can also use a while or do-while loop. Now, based on this method we will develop a prime number program in java using the Scanner.

import java.util.Scanner;

public class PrimeNumber {

  public static boolean isPrime(int number){

     // negative numbers, 0 and 1 are 
     // not a prime number
     if( number <= 1 ) return false;

     // 2 and 3 are prime numbers
     if( number <= 3 ) return true;

     // numbers divisible by 2 and 3
     // are not prime number
     if(number%2==0 || number%3==0)
         return false;

     // logic for remaining numbers
     for(int i=5; i<=Math.sqrt(number); i=i+6){
        if(number%i == 0 || number%(i+2) == 0) 
            return false;
     }

     return true;
  }

  public static void main(String[] args) {

      // declare variables
      int number = 0;
      boolean isPrime = false;

      // create Scanner class object
      Scanner scan = new Scanner(System.in);

      // read number
      System.out.print("Enter a number:: ");
      number = scan.nextInt();

      // check number is prime number or not
      isPrime = isPrime(number);

      // display result
      if(isPrime) // true
         System.out.println(number+
                  " is a prime number");
      else 
         System.out.println(number+
                  " is not a prime number");

      // close Scanner class object
      scan.close();
  }
}

Output:-

Enter a number:: 11
11 is a prime number

Enter a number:: 9
9 is not a prime number

The time complexity for this solution is O(√n).

The prime number using recursion in Java

import java.util.Scanner;

public class PrimeNumber {

  public static boolean isPrime(int number, int i){

     // negative numbers, 0 and 1 are 
     // not a prime number
     if( number <= 2 )
       return (number != 2) ? false : true;

     if( number % i == 0 ) return false;
     if( i*i > number ) return true;

     // check for the next
     return isPrime(number, i+1);
  }

  public static void main(String[] args) {

      // declare variables
      int number = 0;
      boolean flag = false;

      // create Scanner class object
      Scanner scan = new Scanner(System.in);

      // read number
      System.out.print("Enter a number:: ");
      number = scan.nextInt();

      // check number is prime number or not
      flag = isPrime(number, 2);

      // display result
      if(flag) // true
          System.out.println(number+
                  " is a prime number");
      else 
          System.out.println(number+
                   " is not a prime number");

      // close Scanner class object
      scan.close();
   }
}

Program to print first 10 prime numbers in Java

public class PrintPrimeNumber {

  public static boolean isPrime(int number) {

    /* Negative numbers, 0 and 1 
    * are not a prime number
    * 
    * Even numbers (except 2) are
    * also not a prime number
    */
    if(number == 2) return true;
    else if(number<=1 || number%2==0)
         return false;

    // logic for remaining numbers
    for(int i=3; i<=Math.sqrt(number); i++){
         if(number%i == 0) return false;
    }

    return true;
  }

  public static void main(String[] args) {

    System.out.println(
      "First 10 prime numbers in Java are::");

    // variables
    int i=1, count=0;

    // loop to repeat the process
    while(count<10) {
       if(isPrime(i)) {
          System.out.print( i + " ");
          count++;
       }
       i++;
    }
  }
}

Output:-

First 10 prime numbers in Java are::
2 3 5 7 11 13 17 19 23 29

Java program to print prime numbers between two given numbers

The previous program print the first 10 prime numbers in Java. Similar to that program we can write a program to print prime numbers between two numbers for example:- program to print prime numbers from 1 to 100 in java.

import java.util.Scanner;

public class PrimeNumberInRange {

  public static boolean isPrime(int number) {

    /* Negative numbers, 0 and 1 
     * are not a prime number
     * 
     * Even numbers (except 2) are
     * also not a prime number
     */
     if(number == 2) return true;
     else if(number<=1 || number%2==0)
         return false;

     // logic for remaining numbers
     for(int i=3; i<=Math.sqrt(number); i++) {
         if(number%i == 0) return false;
     }

     return true;
  }

  public static void main(String[] args) {

     // declare variables
     int minRange , maxRange;

     // create Scanner class object
     Scanner scan = new Scanner(System.in);

     // read inputs
     System.out.print("Enter min Range value::");
     minRange = scan.nextInt();
     System.out.print("Enter max Range value::");
     maxRange = scan.nextInt();

     // check in range
     System.out.println("Prime numbers from "+
              minRange+" to "+maxRange+" :: ");
     for(int i = minRange; i<= maxRange; i++)
        if(isPrime(i)) 
           System.out.print( i + " ");

     // close Scanner class object
     scan.close();
  }
}

The output for different test-cases are:-

Enter min Range value:: 1
Enter max Range value:: 100
Prime numbers from 1 to 100::
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

Enter min Range value:: 100
Enter max Range value:: 200
Prime numbers from 100 to 200::
101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199

---

If you enjoyed this post, share it with your friends. Do you want to share more information about the topic discussed above or do you find anything incorrect? Let us know in the comments. Thank you!

Search