2523.范围内最接近的两个质数

链接：2523.范围内最接近的两个质数
难度：Medium
标签：数学、数论
简介：请你返回正整数数组 ans = [nums1, nums2] 。

题解 1 - cpp

• 编辑时间：2023-01-01
• 执行用时：248ms
• 内存消耗：10.2MB
• 编程语言：cpp
• 解法介绍：计算质数表后统计。

class Solution {
public:
    int dp[1000005] = {0};
    int left, right;
    void load() {
        for (int i = 2; i <= right; i++) {
            if (dp[i] == 0) dp[++dp[0]] = i;
            for (int j = 1; j <= dp[0] && i * dp[j] < 1000005; j++) {
                dp[i * dp[j]] = 1;
                if (i % dp[j] == 0) break;
            }
        }
    }
    vector<int> closestPrimes(int left, int right) {
        this->left = left;
        this->right = right;
        load();
        int start = 1;
        while (start <= dp[0] && dp[start] < left) start++;
        start++;
        vector<int> ans(2, -1);
        if (start > dp[0]) return ans;
        ans[0] = dp[start - 1]; ans[1] = dp[start];
        for (int i = start + 1; i <= dp[0] && dp[i] <= right; i++) {
            if (dp[i] - dp[i - 1] < ans[1] - ans[0]) {
                ans[0] = dp[i - 1];
                ans[1] = dp[i];
            }
        }
        return ans;
    }
};

题解 2 - rust

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

impl Solution {
    pub fn closest_primes(left: i32, right: i32) -> Vec<i32> {
        let primes = Solution::get_primes(right as usize);
        let mut start = 1;
        while start <= primes[0] && primes[start] < left as usize {
            start += 1;
        }
        let mut ans: Vec<i32> = vec![-1; 2];
        if start + 1 <= primes[0] {
            start += 1;
            ans[0] = primes[start - 1] as i32;
            ans[1] = primes[start] as i32;
            while start + 1 <= primes[0] {
                start += 1;
                if ((primes[start] - primes[start - 1]) as i32) < ans[1] - ans[0] {
                    ans[0] = primes[start - 1] as i32;
                    ans[1] = primes[start] as i32;
                }
            }
        }
        ans
    }
    fn get_primes(max: usize) -> Vec<usize> {
        let mut ans = vec![0; 1000005];
        for i in 2..=max {
            if ans[i] == 0 {
                ans[0] += 1;
                let idx = ans[0];
                ans[idx] = i;
            }
            for j in 1..=ans[0] {
                if ans[j] * i >= 1000005 {
                    break;
                }
                let idx = ans[j] * i;
                ans[idx] = 1;
                if i % ans[j] == 0 {
                    break;
                }
            }
        }
        ans
    }
}