[C++/Java/Python] || Beat 100% || Easy Intuition || Sieve of Eratosthenes algorithm
Intuition\nuse seive Algorithm to find prime numbers and then chek the given condition\n\n# Complexity\n- Time complexity: O(n log log n)\n\n# C++ Code\n\nclass
# Intuition\nuse seive Algorithm to find prime numbers and then chek the given condition\n\n# Complexity\n- Time complexity: O(n log log n)\n\n# C++ Code\n```\nclass Solution {\npublic:\n    vector<vector<int>> findPrimePairs(int n) {\n        bool prime[n + 1]; // Array to store whether a number is prime or not\n        memset(prime, true, sizeof(prime)); // Initializing all numbers as prime\n        prime[1] = false; // 1 is not a prime number\n        prime[0] = false; // 0 is not a prime number\n\n        // Finding prime numbers using Sieve of Eratosthenes algorithm\n        for (int p = 2; p * p <= n; p++) {\n            if (prime[p] == true) {\n                // Marking multiples of p as non-prime\n                for (int i = p * p; i <= n; i += p)\n                    prime[i] = false;\n            }\n        }\n        vector<vector<int>> ans; // Vector to store the pairs of prime numbers\n        for(int i=2;i <= (n-1);i++){\n            int j = n - i; // Finding the complement of i to make the sum n\n            if(prime[i] && prime[j] && i <= j){\n                vector<int> temp = {i,j}; // Creating a pair of prime numbers\n                ans.push_back(temp); // Adding the pair to the result vector\n            }\n        }\n        return ans; // Returning the vector of prime pairs\n    }\n};\n```\n# Java Code\n```\nclass Solution {\n    public List<List<Integer>> findPrimePairs(int n) {\n        boolean[] prime = new boolean[n + 1]; // Array to store whether a number is prime or not\n        List<List<Integer>> ans = new ArrayList<>(); // List to store the pairs of prime numbers\n        \n        // Initializing all numbers as prime\n        for (int i = 2; i <= n; i++) {\n            prime[i] = true;\n        }\n        \n        prime[1] = false; // 1 is not a prime number\n        prime[0] = false; // 0 is not a prime number\n        \n        // Finding prime numbers using the Sieve of Eratosthenes algorithm\n        for (int p = 2; p * p <= n; p++) {\n            if (prime[p]) {\n                // Marking multiples of p as non-prime\n                for (int i = p * p; i <= n; i += p) {\n                    prime[i] = false;\n                }\n            }\n        }\n        \n        for (int i = 2; i <= n - 1; i++) {\n            int j = n - i; // Finding the complement of i to make the sum n\n            if (prime[i] && prime[j] && i <= j) {\n                List<Integer> temp = new ArrayList<>(); // Creating a pair of prime numbers\n                temp.add(i);\n                temp.add(j);\n                ans.add(temp); // Adding the pair to the result list\n            }\n        }\n        \n        return ans; // Returning the list of prime pairs\n    }\n}\n```\n# Python\n```\nclass Solution(object):\n    def findPrimePairs(self, n):\n        prime = [True] * (n + 1)  # List to store whether a number is prime or not\n        ans = []  # List to store the pairs of prime numbers\n        \n        # Initializing all numbers as prime\n        for i in range(2, n + 1):\n            prime[i] = True\n        \n        prime[1] = False  # 1 is not a prime number\n        prime[0] = False  # 0 is not a prime number\n        \n        # Finding prime numbers using the Sieve of Eratosthenes algorithm\n        p = 2\n        while p * p <= n:\n            if prime[p]:\n                # Marking multiples of p as non-prime\n                for i in range(p * p, n + 1, p):\n                    prime[i] = False\n            p += 1\n        \n        for i in range(2, n):\n            j = n - i  # Finding the complement of i to make the sum n\n            if prime[i] and prime[j] and i <= j:\n                temp = [i, j]  # Creating a pair of prime numbers\n                ans.append(temp)  # Adding the pair to the result list\n        \n        return ans  # Returning the list of prime pairs\n\n\n\n```
['Math', 'Two Pointers', 'Python', 'C++', 'Java']