Given a non-negative integer **n** check if it is a **prime number**

Prime numbers are positive numbers greater than 1 that are divisible **only** by 1 and the number itself.

Examples of prime numbers: 2, 3, 5, 7, 11, 13, 17, 19, 23

**Example 1:**

Input:n= 31Output:true

**Example 2:**

Input:n= 6Output:falseExplanation:6 is divisible by 2 and 3.

Your algorithm should run in **O(n)** time and use **O(1)** space.

The task is to determine if a given non-negative integer **n** is a prime number. A prime number is a positive integer greater than 1 that has no positive divisors other than 1 and itself.

- A non-negative integer
**n**.

- A boolean value:
`true`

if**n**is a prime number,`false`

otherwise.

- The input integer
**n**is non-negative.

Input:n = 31Output:true

Input:n = 6Output:falseExplanation:6 is divisible by 2 and 3.

The core challenge is to efficiently determine if a number is prime. Prime numbers have significant applications in fields such as cryptography, number theory, and computer science. A common pitfall is to assume that checking divisibility up to **n-1** is necessary, which can be optimized.

To solve this problem, we can start with a naive approach and then optimize it.

The naive solution involves checking if **n** is divisible by any number from 2 to **n-1**. If we find any such divisor, **n** is not prime.

```
public boolean isPrime(int n) {
if (n <= 1) {
return false;
}
for (int i = 2; i < n; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
```

This approach has a time complexity of **O(n)**, which is not optimal for large values of **n**.

We can optimize the solution by reducing the number of checks. Instead of checking up to **n-1**, we only need to check up to the square root of **n**. This is because if **n** is divisible by any number greater than its square root, it must also be divisible by a number smaller than its square root.

```
public boolean isPrime(int n) {
if (n <= 1) {
return false;
}
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
```

Here is a step-by-step breakdown of the optimized algorithm:

- Check if
**n**is less than or equal to 1. If so, return`false`

. - Iterate from 2 to the square root of
**n**. - For each number
**i**, check if**n**is divisible by**i**. - If a divisor is found, return
`false`

. - If no divisors are found, return
`true`

.

Below is the Java implementation of the optimized solution:

```
public class PrimeChecker {
// Function to check if a number is prime
public boolean isPrime(int n) {
// Check if n is less than or equal to 1
if (n <= 1) {
return false;
}
// Iterate from 2 to the square root of n
for (int i = 2; i * i <= n; i++) {
// Check if n is divisible by i
if (n % i == 0) {
return false;
}
}
// If no divisors are found, n is prime
return true;
}
// Main method to test the function
public static void main(String[] args) {
PrimeChecker checker = new PrimeChecker();
System.out.println(checker.isPrime(31)); // Output: true
System.out.println(checker.isPrime(6)); // Output: false
}
}
```

The time complexity of the optimized solution is **O(√n)** because we only iterate up to the square root of **n**. The space complexity is **O(1)** as we are not using any extra space.

Consider the following edge cases:

**n = 0**: Should return`false`

.**n = 1**: Should return`false`

.**n = 2**: Should return`true`

(2 is the smallest prime number).

To test the solution comprehensively, consider the following test cases:

System.out.println(checker.isPrime(0)); // Output: false System.out.println(checker.isPrime(1)); // Output: false System.out.println(checker.isPrime(2)); // Output: true System.out.println(checker.isPrime(17)); // Output: true System.out.println(checker.isPrime(18)); // Output: false

When approaching such problems, consider the following tips:

- Understand the problem requirements and constraints.
- Start with a naive solution and then look for optimizations.
- Break down the problem into smaller, manageable parts.
- Consider edge cases and test your solution thoroughly.

In this blog post, we discussed how to determine if a number is prime using an optimized approach in Java. We covered the problem definition, approach, algorithm, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is crucial for developing strong problem-solving skills.

For further reading and practice, consider the following resources: