2761.和等于目标值的质数对

链接：2761.和等于目标值的质数对
难度：Medium
标签：数组、数学、枚举、数论
简介：给你一个整数 n 。请你以二维有序列表的形式返回符合题目要求的所有 [xi, yi] ，列表需要按 xi 的 非递减顺序 排序。如果不存在符合要求的质数对，则返回一个空数组。

题解 1 - cpp

• 编辑时间：2023-07-02
• 执行用时：1256ms
• 内存消耗：110.4MB
• 编程语言：cpp
• 解法介绍：线性筛。

unordered_set<int> s;
vector<int> get_primes(int n) {
    vector<int> primes(n, 0);
    for (int i = 2; i < n; i++) {
        if (primes[i] == 0) {
            primes[++primes[0]] = i;
            s.insert(i);
        }
        for (int j = 1; j <= primes[0] && i * primes[j] < n; j++) {
            primes[i * primes[j]] = 1;
            if (i % primes[j] == 0) break;
        }
    }
    return primes;
}
vector<int> primes = get_primes(10000000);
class Solution {
public:
    vector<vector<int>> findPrimePairs(int n) {
        vector<vector<int>> res;
        if (s.count(n - 2)) res.push_back({2, n - 2});
        for (int i = 3; i <= n / 2; i += 2) {
            if (!s.count(i) || !s.count(n - i)) continue;
            res.push_back({i,n-i});
        }
        return res;
    }
};

题解 2 - cpp

• 编辑时间：2023-07-02
• 执行用时：364ms
• 内存消耗：32.4MB
• 编程语言：cpp
• 解法介绍：埃氏筛。

vector<bool> get_primes2(int n) {
    vector<bool> primes(n + 3, true);
    primes[0] = primes[1] = false;
    for (int i = 2; i < n; i++) {
        if (!primes[i]) continue;
        for (int j = 2; i * j < n; j++) {
            primes[i * j] = false;
        }
    }
    return primes;
}
class Solution {
public:
    vector<vector<int>> findPrimePairs(int n) {
        auto primes = get_primes2(n);
        vector<vector<int>> res;
        if (n >= 2 && primes[n - 2]) res.push_back({ 2, n - 2 });
        for (int i = 3; i <= n / 2; i += 2) {
            if (primes[i] && primes[n - i]) {
                res.push_back({ i, n - i });
            }
        }
        return res;
    }
};

题解 3 - python

• 编辑时间：2023-07-02
• 执行用时：744ms
• 内存消耗：27.6MB
• 编程语言：python
• 解法介绍：同上。

def get_primes2(n: int) -> List[bool]:
        n += 3
        primes = [True for _ in range(n)]
        primes[0] = primes[1] = False
        for i in range(2, n):
            if primes[i]:
                j = 2
                while i * j < n:
                    primes[i*j] = False
                    j += 1
        return primes
    
    primes = get_primes2(1000000)
    
    class Solution:
        def findPrimePairs(self, n: int) -> List[List[int]]:
            res = []
            if n >= 2 and primes[n-2]:
                res.append([2, n-2])
            for i in range(3, n//2 + 1, 2):
                if primes[i] and primes[n-i]:
                    res.append([i, n-i])
            return res

题解 4 - rust

• 编辑时间：2023-07-02
• 执行用时：224ms
• 内存消耗：3.6MB
• 编程语言：rust
• 解法介绍：同上。

pub fn get_primes2(mut n: usize) -> Vec<bool> {
    n += 3;
    let mut primes = vec![true; n];
    primes[0] = false;
    primes[1] = false;
    for i in 2..n {
        if primes[i] {
            let mut j = 2;
            while i * j < n {
                primes[i * j] = false;
                j += 1;
            }
        }
    }
    primes
}
impl Solution {
    pub fn find_prime_pairs(n: i32) -> Vec<Vec<i32>> {
        let n = n as usize;
        let primes = get_primes2(n);
        let mut res = vec![];
        if n >= 2 && primes[n - 2] {
            res.push(vec![2, (n as i32) - 2]);
        }
        let mut i = 3;
        while i <= n / 2 {
            if primes[i] && primes[n - i] {
                res.push(vec![i as i32, (n - i) as i32]);
            }
            i += 2;
        }
        res
    }
}