Sieve of Eratosthenes With Similar Problems | Beat 100% 🏆
Intuition\n\nThis is a variation of the Sieve of Eratosthenes algorithm.\n\nThe Sieve of Eratosthenes is one of the oldest-known algorithms to human civilizatio
# Intuition\n\nThis is a variation of the Sieve of Eratosthenes algorithm.\n\nThe Sieve of Eratosthenes is one of the oldest-known algorithms to human civilization, used to find the **prime numbers** up to any given limit. The algorithm is attributed to a third-century BCE Greek astronomer, mathematician, geographer, and historian, Eratosthenes. The way the algorithm works is pretty intuitive.\n\n<a href="//upload.wikimedia.org/wikipedia/commons/b/b9/Sieve_of_Eratosthenes_animation.gif"><img alt="File:Sieve of Eratosthenes animation.gif" src="//upload.wikimedia.org/wikipedia/commons/b/b9/Sieve_of_Eratosthenes_animation.gif" decoding="async" width="445" height="369" data-file-width="445" data-file-height="369"></a>\n**Image Reference: Wikipedia**\n\n# Similar Problems:\n- [204. Count Primes](https://leetcode.com/problems/count-primes/)\n- [263. Ugly Number](https://leetcode.com/problems/ugly-number/)\n- [264. Ugly Number II](https://leetcode.com/problems/ugly-number-ii/)\n- [279. Perfect Squares](https://leetcode.com/problems/perfect-squares/)\n- [2427. Number of Common Factors](https://leetcode.com/problems/number-of-common-factors/)\n\n# Complexity\n- Time complexity: $$O(N\\log(\\log N))$$\nThe time complexity to define Sieve prime array is $$O(N\\log(\\log N))$$.\nTwo sum calculation array iterates for $$O(\\frac{N}{2}+1)$$ time.\nTotal, $$O(N\\log(\\log N))$$ is required.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(N)$$\nWe have declared an array of size $$N$$.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n``` Java []\nclass Solution {    \n    public List<List<Integer>> findPrimePairs(int n) {\n        boolean[] prime = new boolean[n + 1];\n        // by initialization they are all false, so need to make true\n        Arrays.fill(prime, true);\n  \n        for (int p = 2; p * p <= n; p++) {\n            if (prime[p] == true) {\n                for (int i = p * p; i <= n; i += p)\n                    prime[i] = false;\n            }\n        }\n        List<List<Integer>> ans = new ArrayList<>();\n        // start from 2 because, 1 cannot be prime\n        // end before n/2+1 because, then we will have repeating pairs\n        for(int i=2; i<n/2+1; i++) {\n            if(prime[i] && prime[n-i]){\n                ans.add(Arrays.asList(i, n-i));\n            }\n        }\n        return ans;\n    }\n}\n```
['Math', 'Enumeration', 'Number Theory', 'C++', 'Java']