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 ≤ 109
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.
