**1. What is a prime number?**

A **prime number** is a positive integer that can only be divided by 1 and itself. **For example**, 2, 3, 5, 7, 11, 13, 17, 19, 23, etc. are prime numbers.

Note: 0 and 1 are not prime numbers.

**How to check if a positive integer n is a prime number?**

- If n is 0 or 1, it is not a prime number.
- If n
**is not divisible**by any number from 2 to n-1, then n is a prime number. Otherwise, n is not a prime number.

**It is easy to see** that only 2 is an even prime number, all other even numbers are not prime because they are divisible by 2. Therefore, instead of checking from 2 to n-1, we can only consider from 2 to n/2.

**In addition**, it has been proven that: **we only need to check if n is divisible by any number from 2 to the square root of n** to determine if n is a prime number or not.

**2. How to check prime numbers in Java**

**Using a for loop in Java to check if n is divisible by any number from 2 to n-1 or not?**

```
package primenumber;
import java.util.Scanner;
public class PrimeNumber {
public static void main(String[] args) {
int num;
boolean is_prime = true;
System.out.print("Enter a positive integer: ");
try (Scanner scanner = new Scanner(System.in)) {
num = scanner.nextInt();
}
// 0 and 1 are not prime numbers
if (num == 0 || num == 1) {
is_prime = false;
}
// loop to check if n is prime
for (int i = 2; i <= num-1; i++) {
if (num % i == 0) {
is_prime = false;
break;
}
}
if (is_prime) {
System.out.print(num + " is a prime number");
} else {
System.out.print(num + " is not a prime number");
}
}
}
```

In this program, we take a number as input from the user and then check whether it is prime or not by dividing it by all possible divisors from **2 to num-1**. If the number is divisible by any of these divisors, then it is not a prime number. If none of these divisors can divide the number, then it is a prime number.

We use a boolean variable `is_prime`

to keep track of whether the number is prime or not. We initially assume that the number is prime and set

to `is_prime`

`true`

. If we find a divisor that divides the number, then we assigned the value `false`

to `is_prime`

.

At the end of the program, we check the value

to determine whether the number is prime or not.`is_prime`

**We can change the loop condition to only run from 2 to n/2.**

```
// loop to check if n is prime
for (int i = 2; i <= num/2; i++) {
if (num % i == 0) {
is_prime = false;
break;
}
}
```

**You can change the loop condition to only run from 2 to the square root of n ( Math.sqrt(n)).**

```
// loop to check if n is prime
for (int i = 2; i <= Math.sqrt(num); i++) {
if (num % i == 0) {
is_prime = false;
break;
}
}
```

We should only iterate up to the square root of n to make the loop shorter.

These are three ways how to check prime numbers in Java. The last way is usually the most optimal one for most cases.