You are given an integer n. We say that two integers x and y form a prime number pair if:
1 <= x <= y <= nx + y == nx and y are prime numbersReturn the 2D sorted list of prime number pairs [xi, yi]. The list should be sorted in increasing order of xi. If there are no prime number pairs at all, return an empty array.
Note: A prime number is a natural number greater than 1 with only two factors, itself and 1.
Example 1:
Input: n = 10 Output: [[3,7],[5,5]] Explanation: In this example, there are two prime pairs that satisfy the criteria. These pairs are [3,7] and [5,5], and we return them in the sorted order as described in the problem statement.
Example 2:
Input: n = 2 Output: [] Explanation: We can show that there is no prime number pair that gives a sum of 2, so we return an empty array.
Constraints:
1 <= n <= 106This approach involves generating all prime numbers using the Sieve of Eratosthenes up to n. Then, iterate through the list of primes and for each prime x, check if (n - x) is also a prime and greater than or equal to x to form a valid pair.
This solution uses the Sieve of Eratosthenes to compute a list of prime numbers up to n. We then iterate over possible x values, checking that both x and y (where y = n - x) are prime, and that x <= y. We print the pair if both are true.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log log n) due to the sieve and O(n) for pair checking, leading to overall O(n log log n).
Space Complexity: O(n) for the boolean array storing prime status.
This alternative approach uses trial division to check each potential pair [x, y] for primality, leveraging the fact that x + y = n implies y = n - x. By iterating with x up to n/2, we minimize redundant checks.
This C implementation uses trial division to check each x and corresponding y for primality, iterating up to n/2 to find valid pairs quickly but potentially less efficiently than a sieve approach for large n.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n√n) due to trial division checks for primality.
Space Complexity: O(1) as no extra data structures are used for storing primes.
| Approach | Complexity |
|---|---|
| Sieve of Eratosthenes with Pair Search | Time Complexity: O(n log log n) due to the sieve and O(n) for pair checking, leading to overall O(n log log n). |
| Trial Division with Reduction | Time Complexity: O(n√n) due to trial division checks for primality. |
This is the Most Asked FAANG Interview Question! - Two Sum - Leetcode 1 • Greg Hogg • 649,211 views views
Watch 9 more video solutions →Practice Prime Pairs With Target Sum with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor