Start learning free

LESSON 135 OF 410 · LOOPS & CONDITIONALS

Prime Number in Java with O(n) Time Complexity

Practice Read the full explanation

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 = 31
Output: true

Example 2:

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

Note:

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

Hints:

Prime numbers are only divisible by the number 1 or itself. Let's reformulate this definition a little bit:
A number n is prime if and only if there is no such number d such that 1 < d < n and d is a divisor of n. Is this new definition more helpful?

We should iterate through each number d from 2 to n - 1 and check if d is a divisor of n.
If we find such a number, we can conclude that n is not prime and return false right away:

for each d : 2 -> n - 1:
	if d is divisor of n:
		return false

How do we check if d is divisor of n? When should we return true?

d is divisor of n (or n is a multiple of d) if and only if n % d == 0:

for each d : 2 -> n - 1:
	if n % d == 0:
		return false
return true

As you can see, if the for loop terminates and we reach the return true line of code, we know that we haven't found a divisor, so it's safe to say n is prime.

We have a for loop that performs exactly n - 2 iterations, thus the Time Complexity is O(n).
The only extra space we use is the iterator variable d inside the loop, thus the Extra Space used is O(1).

STEP 1 OF 4

Guided

Ctrl + Enter to check

JAVA · LOOPS & CONDITIONALS

Prime Number in Java, explained

Problem Definition

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.

Input

A non-negative integer n.

Output

A boolean value: true if n is a prime number, false otherwise.

Constraints

The input integer n is non-negative.

Example

Input: n = 31
Output: true

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

Understanding the Problem

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.

Approach

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

Naive Solution

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.

Optimized Solution

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

Algorithm

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.

Code Implementation

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
    }
}

Complexity Analysis

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.

Edge Cases

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

Testing

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

Thinking and Problem-Solving Tips

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.

Conclusion

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.

Additional Resources

For further reading and practice, consider the following resources:

Keep going with JavaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free