•Better than 97.12%
•Runtime is 65 ms
•Time Complexity is O(sqrt(n))
bool isPrime(int n) {
// Check if the number is less than or equal to 1; if so, it is not prime
if (n <= 1) {
return false; // 0 and 1 are not prime numbers
}
// Check if n is 2, which is the only even prime number
if (n == 2) {
return true; // 2 is prime
}
// If n is even and greater than 2, it cannot be prime
if (n % 2 == 0) {
return false; // Exclude all even numbers greater than 2
}
// Loop through odd numbers from 3 to the square root of n
for (int i = 3; i * i <= n; i += 2) {
// Check if i is a divisor of n
if (n % i == 0) {
return false; // If n is divisible by any odd number, it's not prime
}
}
// If no divisors were found, n is prime
return true; // n has no divisors other than 1 and itself
}