Linear Sieve | O(1) primality check | prunning | Beats 99.76% by runtime | small code
Approach\nUse linear sieve to find all prime upto 10^6, p contains primes and isp[i] to check if number i is prime or not. In function findPrimePairs(int n) ite
# Approach\nUse linear sieve to find all prime upto `10^6`, `p` contains primes and `isp[i]` to check if number `i` is prime or not. In function `findPrimePairs(int n)` iterate just over prime less than n and for each prime `e` check if `n-e` is prime or not by using array `isp[i]`, if yes push `[e, n-e]` if not go to next prime, and if `(n-e)<e` then break because for the later primes that satisfy the above condition `e` would be greater than `(n-e)`, but for the valid pairs first number should be smaller than or equal to second number.\n\n# Complexity\n- Time complexity: $$O(no.\\:of\\:primes < n)$$ or $$O(\u03C0(n))$$\n\n- Space complexity: $$O(1)$$ for each testcase.\n\n# Code\n```\n#define pb push_back\nusing ll = long long;\nusing vi = vector<int>;\nconst int mxn = 1e6 + 10;\nvi p, isp(mxn, 1);\n\nvoid init(){\n    if(isp[0]==0)return;\n    isp[0] = isp[1] = 0;\n    for(int i=2;i<mxn;i++){\n        if(isp[i])p.pb(i);\n        for(int j=0;j<p.size() && (i*1ll*p[j])<(mxn*1ll);j++){\n            isp[p[j] * i] = 0;\n            if(i % p[j])continue;\n            break;\n        }\n    }\n}\n\nclass Solution {\npublic:\n    vector<vector<int>> findPrimePairs(int n) {\n        init();\n        vector<vi> ans;\n        for(auto e: p){\n            if((n-e)<e)break;\n            if(isp[n-e])ans.pb({e, n-e});\n        }\n        return ans;\n    }\n};\n```
['C++']