Prime Number in C++ with O(n) Time Complexity

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.

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 integer divisors other than 1 and itself.

Input

A single non-negative integer n.

Output

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

Constraints

0 ≤ n ≤ 10⁹

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 cryptography, number theory, and various algorithms. A common pitfall is to assume that checking divisibility up to n-1 is necessary, which is not optimal.

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.

bool 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 efficient for large values of n.

Optimized Solution

We can optimize the solution by realizing that a larger factor of n must be a multiple of a smaller factor that is less than or equal to √n. Therefore, we only need to check divisibility up to √n.

bool isPrime(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) return false;
    }
    return true;
}

This approach reduces the time complexity to O(√n), making it much more efficient for large values of n.

Algorithm

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

Handle base cases: if n is less than or equal to 1, return false.
If n is 2 or 3, return true (since both are prime).
If n is divisible by 2 or 3, return false.
Iterate from 5 to √n, checking divisibility by i and i+2 (to skip even numbers).
If no divisors are found, return true.

Code Implementation

bool isPrime(int n) {
    // Handle base cases
    if (n <= 1) return false;
    if (n <= 3) return true;
    // Check divisibility by 2 and 3
    if (n % 2 == 0 || n % 3 == 0) return false;
    // Check divisibility from 5 to sqrt(n)
    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) return false;
    }
    return true;
}

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 use a constant amount of extra space.

Edge Cases

Consider the following edge cases:

n = 0: Should return false.
n = 1: Should return false.
n = 2: Should return true (smallest prime number).
n = 4: Should return false (even number greater than 2).

Testing

To test the solution comprehensively, consider a variety of test cases:

int main() {
    // Test cases
    assert(isPrime(0) == false);
    assert(isPrime(1) == false);
    assert(isPrime(2) == true);
    assert(isPrime(3) == true);
    assert(isPrime(4) == false);
    assert(isPrime(31) == true);
    assert(isPrime(37) == true);
    assert(isPrime(49) == false);
    std::cout << "All test cases passed!" << std::endl;
    return 0;
}

Thinking and Problem-Solving Tips

When approaching such problems:

Understand the mathematical properties of the problem.
Start with a brute-force solution and then optimize.
Consider edge cases and test thoroughly.
Practice similar problems to improve problem-solving skills.

Conclusion

Determining if a number is prime is a fundamental problem with various applications. By understanding the properties of prime numbers and optimizing the solution, we can efficiently solve this problem even for large inputs. Practice and thorough testing are key to mastering such problems.