 # Prime Number Program in Java

In this problem section, you will learn to create a prime number program in Java with the help of examples.

## What is a Prime Number?

A prime number is a natural number that is divisible by 1 and itself only. For example, 2, 3, 5, 7, etc. are prime numbers.

Prime numbers are used in cryptography, in order to generate public and private keys for encryption and decryption.

Finding bigger prime numbers is a very difficult task. the biggest prime number as of Sept 2022 is 282,589,933 − 1.

Let's create a simple program to check whether a number is prime or not.

## Java Prime Number Program

Let's create Java programs that check whether a given number is prime or not. We will start with a bruit force approach and will keep making the program more and more efficient.

### Worst Approach

According to the definition, a prime number is only divisible by 1 and the number itself. So the first idea is to divide the given number by all the numbers from 2 to n-1. If the number is divisible by any of the numbers then it is not a prime number.

Let's see the code for this approach.

``````import java.util.Scanner;

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter a number: ");
int n = sc.nextInt();
sc.close();

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

Output:

```Enter a number: 7
7 is a prime number.```

Let's see the time complexity of this program.

The time complexity of this program is O(n). Because we are checking all the numbers from 2 to n-1.

### Better Approach

In the above program, we blindly checked all the numbers from 2 to n-1. But we can optimize this program by checking only till n/2.

When you look closely it is obvious a number can never be divisible by a number greater than n/2.

So instead of checking all the numbers from 2 to n-1, we can check only till n/2.

``````import java.util.Scanner;

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter a number: ");
int n = sc.nextInt();
sc.close();

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

Output:

```Enter a number: 19
19 is a prime number.```

The time complexity of this program is O(n/2). Which is O(n) only. But definitely, this is better than the previous program.

### Best Approach

Now we will see the best approach to check whether a number is prime or not.

We need not even check till n/2. We can check till sqrt(n) only and it will give us the same result.

Thinking how? 🤔

1. Let's say we have a number n. And suppose it is not a prime number.
2. And it has two factors a and b.
3. Here a and b both can never be greater than sqrt(n) because if they are greater than sqrt(n) then a*b will be greater than n.
4. So if we check till sqrt(n) then we will find the factors of n if it is not a prime number.
``````import java.util.Scanner;

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter a number: ");
int n = sc.nextInt();
sc.close();

boolean isPrime = true;
for (int i = 2; i <= Math.sqrt(n); i++) {
if (n % i == 0) {
isPrime = false;
break;
}
}
if (isPrime) {
System.out.println(n + " is a prime number.");
} else {
System.out.println(n + " is not a prime number.");
}
}
}``````

Output:

```Enter a number: 23
23 is a prime number.```

The time complexity of this program is O(sqrt(n)). Which is much better than previous programs.

## Prime Number using Recursion

Let's see how to check whether a number is prime or not using recursion.

Here we will use the same approach as we used in the previous program but we will use recursion.

``````import java.util.Scanner;

public static boolean isPrime(int num, int divisor) {
// base case
if (num <= 2) {
return true;
}
if (divisor <= Math.sqrt(num)) {
if (num % divisor == 0) {
return false;
}
return isPrime(num, divisor + 1);
}
return true;
}

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter a number: ");
int num = sc.nextInt();
sc.close();

if (isPrime(num, 2)) {
System.out.println(num + " is a prime number.");
} else {
System.out.println(num + " is not a prime number.");
}
}
}``````

Output:

```Enter a number: 71
71 is a prime number.```

## Print all the prime numbers between 1 to n

Now we will see how to print all the prime numbers between 1 to n.

Here is the normal approach where we check each number by dividing it with all the numbers from 2 to sqrt(n).

``````import java.util.Scanner;

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter a number: ");
int n = sc.nextInt();
sc.close();

for (int i = 2; i <= n; i++) {
boolean isPrime = true;
for (int j = 2; j <= Math.sqrt(i); j++) {
if (i % j == 0) {
isPrime = false;
break;
}
}
if (isPrime) {
System.out.print(i + " ");
}
}
}
}``````

Output:

```Enter a number: 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```

### Sieve of Eratosthenes

Now we will see the more efficient way to print all the prime numbers between 1 to n.

It is called the Sieve of Eratosthenes. It is a very famous algorithm to find all the prime numbers between 1 to n.

Here we will use a boolean array to mark all the numbers as prime or not prime.

``````import java.util.Scanner;

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter a number: ");
int n = sc.nextInt();
sc.close();

boolean[] isPrime = new boolean[n + 1];
for (int i = 2; i <= n; i++) {
isPrime[i] = true;
}

for (int i = 2; i * i <= n; i++) {
if (isPrime[i]) {
for (int j = i * i; j <= n; j += i) {
isPrime[j] = false;
}
}
}

for (int i = 2; i <= n; i++) {
if (isPrime[i]) {
System.out.print(i + " ");
}
}
}
}``````

Output:

```Enter a number: 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```

The time complexity of this program is O(n*log(log(n))).

## Next Prime Number

Now we will see how to find the next prime number after a given number.

To get the next prime number we will simply increment the given number by 1 and check whether it is prime or not.

``````import java.util.Scanner;

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter a number: ");
int n = sc.nextInt();
sc.close();

int nextPrime = n + 1;
while (true) {
boolean isPrime = true;
for (int i = 2; i <= Math.sqrt(nextPrime); i++) {
if (nextPrime % i == 0) {
isPrime = false;
break;
}
}
if (isPrime) {
System.out.println("Next prime number is: " + nextPrime);
break;
}
nextPrime++;
}
}
}``````

Output:

```Enter a number: 199
Next prime number is: 211```

## Previous Prime Number

Now we will see how to find the previous prime number before a given number.

To get the previous prime number we will simply decrement the given number by 1 and check whether it is prime or not.

``````import java.util.Scanner;

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter a number: ");
int n = sc.nextInt();
sc.close();

int prevPrime = n - 1;
while (true) {
boolean isPrime = true;
for (int i = 2; i <= Math.sqrt(prevPrime); i++) {
if (prevPrime % i == 0) {
isPrime = false;
break;
}
}
if (isPrime) {
System.out.println("Previous prime number is: " + prevPrime);
break;
}
prevPrime--;
}
}
}``````

Output:

```Enter a number: 199
Previous prime number is: 197```

## Conclusion

So this is all about prime numbers. We have covered all necessary topics related to prime numbers. We have various different programs related to the prime numbers in Java.