bool isPrime(int n) { // Corner cases if (n <= 1) return false; if (n <= 3) return true; // This is checked so that we can skip // middle five numbers in below loop // any integer can be expressed as (6k + i), where i = -1, 0, 1, 2, 3, 4 // (6k + 0), (6k + 2), (6k + 4) covered by n%2 // (6k + 3) covered by n%3 if (n % 2 == 0 || n % 3 == 0) return false; // Check for 6K + 1 and 6K - 1 for (int i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return false; return true; }