C++ | Optimised | Beats 100% memory |For Beginners | Easy
PLEASE UPVOTE IF YOU FOUND THIS HELPFUL!\n\n# Approach\n\nIterating until sqrt(n) by checking remainders will give TLE. So we need to optimize further. It can b
**PLEASE UPVOTE IF YOU FOUND THIS HELPFUL!**\n\n# Approach\n\nIterating until sqrt(n) by checking remainders will give TLE. So we need to optimize further. It can be proven that prime numbers (> 3 of course) are of the form 6x+1 or 6x-1. So it is enough to check remainders by numbers of this form.\nWe just check for cases of remainders with 2 and 3 and iterate from here.\n\n       1. Here i is of the form 5 + 6K where K>=0\n       2. i+1, i+3, i+5 are even numbers (6 + 6K). N is not \n          an even number\n       3. Because N%2 and N%3 checks are done in the before step\n       4. Hence i+1, i+3, i+5 can\'t be N\'s divisors.\n       5. i+4 is 9 + 6K which is a 3 multiple. \n       6. N is not a 3 multiple hence i+4 can\'t be it\'s divisor\n    Hence we only check if N is a divisor of i or i+2.\n\n\n\n# Complexity\n- Time complexity:\n$O(n)$\n\n- Space complexity:\n$O(1)$\n\n# Code\n```\nclass Solution {\nprivate:\n    bool isPrime(int n){\n        if (n <= 3)\n            return true;\n        if (n % 2 == 0 || n % 3 == 0)\n            return false;\n        for (int i = 5; i * i <= n; i = i + 6)\n            if (n % i == 0 || n % (i + 2) == 0)\n                return false;\n\n        return true;\n    }\n\npublic:\n    vector<vector<int>> findPrimePairs(int n) {\n        vector<vector<int>> ans;\n        if(n <= 3)  return ans;\n        for(int i=2; i<= n/2; ++i){\n            if(isPrime(i) and isPrime(n-i)) ans.push_back({i, n-i});\n        }    \n        return ans;\n    }\n};\n```
['C++']