**Program to Check Prime Number using a for loop**

Java program to check if a given number is prime using a for loop:

### Java

`import java.util.Scanner;`

class Prime_Number {

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

int num = sc.nextInt();

if(isPrime(num)) {

System.out.println(num + " is a prime number");

} else {

System.out.println(num + " is not a prime number");

}

}

public static boolean isPrime(int num) {

if (num < 2) {

return false;

}

for (int i = 2; i <= Math.sqrt(num); i++) {

if (num % i == 0) {

return false;

}

}

return true;

}

}

**Input**

`13`

**Output**

`13 is a prime number`

**Explanation**

This Java program checks if a given number is prime. It prompts the user for input, then utilizes a `for` loop to iterate from 2 up to the square root of the number. Within each iteration, it checks if the number is divisible by the current value of `i`. If a divisor is found, it concludes the number is not prime. If no divisors are found, it's a prime number.

**Program to Check Prime Number using a while loop**

Java program to check if a given number is prime using a while loop:

### Java

`import java.util.Scanner;`

class PrimeCheck {

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

int num = scanner.nextInt();

if(isPrime(num)) {

System.out.println(num + " is a prime number");

} else {

System.out.println(num + " is not a prime number");

}

}

public static boolean isPrime(int num) {

if (num < 2) {

return false;

}

int i = 2;

while (i <= Math.sqrt(num)) {

if (num % i == 0) {

return false;

}

i++;

}

return true;

}

}

**Input**

`17`

**Output**

`17 is a prime number`

**Explanation**

This Java program checks if a given number is prime using a `while` loop. It starts by prompting the user for input. The `isPrime` method iterates from 2 up to the square root of the number using a `while` loop, checking for divisibility in each iteration. If a divisor is found, it concludes the number is not prime. If no divisors are found, it deems the number as prime.

## Naive Approach for Writing Prime Number Program in Java

As per the definition, A number **n** is a prime number if there is no number b/w one and n that can divide n.

We are going to use this simple fact to write our program.

Code in Java

### Java

`public class PrimeNumber {`

// function to check if a number is prime

private static boolean isPrime(int number){

// variable to store if the number is prime

boolean isNumberPrime = true;

/*

loop in the range [2,number-1] to check

if there is any integer that can divide

the number.

*/

for(int i=2; i<number; i++){

if( (number % i) == 0 ) {

isNumberPrime = false;

break;

}

}

return isNumberPrime;

}

public static void main(String[] args) {

// Defining two number 7 and 8

int number1 = 7;

int number2 = 8;

// checking if they are prime or not

boolean result1 = isPrime(number1);

boolean result2 = isPrime(number2);

// Printing the result

System.out.println(number1+" is "+((result1)? "a Prime number":" not a Prime number"));

System.out.println(number2+" is "+((result2)? "a Prime number":" not a Prime number"));

}

}

**Output**

**Explanation**

We have made **isPrime **function to determine if a number is prime. This function takes a **number **(an integer) as its parameter. Then we loop on the range **two to number-1 **to check if any number divides the â€śnumberâ€ť. If any integer exists between two and number-1 that divides the number, then the â€śnumberâ€ť is not a prime, and hence we assign **isNumberPrime** as false.

**Time and Space Complexity**

- Looping over the range [2, number-1] will take O(n) operations, and hence the time complexity is O(n).
- We are not using any extra space except for variables like isNumberPrime; hence, the space complexity is O(1).

## Optimised Approach to Write Prime Number Program in Java

Letâ€™s see the factors of a number to find some pattern:

`36 = (1,2,3,4),(6),(36,18,12,9).`

We have kept factors of 36 in three groups. If we multiply a member of the first group by the respective member of the second group, we will get 36, i.e.

`1*36 = 36, 2*18 = 36, 3*12 = 36, 4*9 = 36.`

So, when we check that if 36 is divisible by the member of the first group, then we are not required to check the same by the second group. This led to the observation that we only need to check factors until sqrt(n) to determine whether it is prime.

Letâ€™s verify the fact with another number, 12.

`12 = (1,2,3),(12,6,4).`

We have only two groups in this case because 12 is not a perfect square. Here also, multiplying the respective members of the first and second groups will result in 12. So, we only need to check factors until sqrt(12) ~ 3 to determine whether it is prime.

Code in Java

### Java

`public class PrimeNumber {`

// function to check if a number is prime

private static boolean isPrime(int number){

// variable to store if the number is prime

boolean isNumberPrime = true;

/*

loop in the range [2,sqrt(n)] to check

if there is any odd integer that can divide

the number.

*/

for(int i = 2; i * i <= number; i++ ){

if( (number % i) == 0 ) {

isNumberPrime = false;

break;

}

}

return isNumberPrime;

}

public static void main(String[] args) {

// Defining two number 49456 and 123677

int number1 = 49456;

int number2 = 123677;

// checking if they are prime or not

boolean result1 = isPrime(number1);

boolean result2 = isPrime(number2);

// Printing the result

System.out.println(number1+" is "+((result1)? "a Prime number": "not a Prime number"));

System.out.println(number2+" is "+((result2)? "a Prime number": "not a Prime number"));

}

}

**Output**

**Explanation**

We have made isPrime function to determine if a number is a prime. This function takes a number (an integer) as its parameter. Then we loop on the range two to sqrt(n) to check if any integer exists that divides the number, then the â€śnumberâ€ť is not a prime, and hence we assign isNumberPrime as false. We are using the expression **i * i <= number **to stop the execution of the loop when the integer lies outside the mentioned range.

**Time and Space Complexity**

- Looping over the range [2, sqrt(n)] will take O(sqrt(n)) operations, and hence the time complexity is O(sqrt(n)).
- We are not using any extra space except for variables like isNumberPrime; hence, the space complexity is O(1).

## Frequently Asked Questions

**How do you write a prime number program in Java?**

In Java, write a program that iterates through numbers, checking for factors up to their square root. If a number has no factors other than 1 and itself, it's prime.

**What is the method to find a prime number in Java?**

The method involves iterating from 2 to the square root of the number and checking for divisibility. If the number is only divisible by 1 and itself, it's prime.

**What are the first 10 prime numbers print? **

The first ten prime numbers are: 2, 3, 5, 7, 11, 13, 17, 19, 23, and 29. These are natural numbers greater than 1 that have no divisors other than 1 and themselves.

**What is the logic of a prime number?**

A prime number is one that's only divisible by 1 and itself. To determine if a number is prime, iterate from 2 to its square root. If it's divisible by any number in this range, it's not prime; otherwise, it is.

## Conclusion

In conclusion, we can say that prime number program in java are very important in computer science. They have diverse applications. We can find if a number is prime using various approaches. In this article, we improved approach by approach, and, finally, the most optimised algorithm has taken O(sqrt(n)) operations to determine if a number is prime.

Refer to our __guided paths on Coding Ninjas Studio__ to learn more about DSA, Competitive Programming, JavaScript, System Design, etc.

Happy Learning!