2761. Prime Pairs With Target Sum

Question

You are given an integer n. We say that two integers x and y form a prime number pair if:

• 1 <= x <= y <= n
• x + y == n
• x and y are prime numbers

Return 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.

Solution

通过线性筛（Linear Sieve）筛选素数。

用一个数组标记是否为素数。用一个列表记录素数。

首先将所有的数字标记为素数。

遍历，从2开始进行筛查，如果当前位置为素数，则加入素数列表。

从素数列表中选择素数prime，与当前数字i相乘得到合数prime * i，将对应的数组位置标记为false。

当i以prime取模为0时（i可以整除prime），停止筛查。更大的合数prime * i 将会在未来的遍历被prime’ * i‘（prime’ < prime, i’ > i）筛掉。

Code

class Solution {
    boolean[] isPrime;
    List<Integer> primes = new ArrayList<Integer>();
    public List<List<Integer>> findPrimePairs(int n) {
        List<List<Integer>> ret = new ArrayList<>();
        
        isPrime = new boolean[n];
        Arrays.fill(isPrime, true);
        countPrimes(n);
        for(int i = 0; i < primes.size(); i++){
            int x = primes.get(i);
            int y = n - x;
            if(y < x) break;
            if(!isPrime[y]) continue;
            List<Integer> temp = new ArrayList<Integer>();
            temp.add(x);
            temp.add(y);
            ret.add(temp);
        }
        return ret;
    }
    
    public void countPrimes(int n){
        for(int i = 2; i < n; i++){
            if(isPrime[i]){
                primes.add(i);
            }
            for(int prime : primes){
                if(prime * i >= n) break;
                isPrime[prime * i] = false;
                if(i % prime == 0) break;
            }
        }
    }
}

class Solution:
    def findPrimePairs(self, n: int) -> List[List[int]]:
        ret = []
        is_primes = [True] * n
        primes = []
        for i in range(2, n):
            if is_primes[i]:
                primes.append(i)
            for p in primes:
                if p * i >= n:
                    break
                is_primes[p * i] = False
                if i % p == 0:
                    break
        
        for x in primes:
            if x > n/2:
                break
            y = n - x
            if not is_primes[y]:
                continue
            ret.append([x, y])
        
        return ret