# 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);

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

### 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 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);

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

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

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!