题目描述

给你一个整数数组 nums。

返回两个（不一定不同的）素数在 nums 中 下标 的 最大距离。

样例

输入：nums = [4,2,9,5,3]

输出：3

解释：nums[1]、nums[3] 和 nums[4] 是素数。因此答案是 |4 - 1| = 3。

输入：nums = [4,8,2,8]

输出：0

解释：nums[2] 是素数。因为只有一个素数，所以答案是 |2 - 2| = 0。

限制

• 1 <= nums.length <= 3 * 10^5
• 1 <= nums[i] <= 100
• 输入保证 nums 中至少有一个素数。

算法

(预处理，前后遍历) $O(m + n)$

1. 使用线性筛全局预处理素数数组。
2. 分别从前后遍历数组，找到第一个以及最后一次素数的出现位置，然后作差得到答案。

时间复杂度

• 预处理的时间复杂度为 $O(m)$，其中 $m$ 为最大可能的数字。
• 前后遍历的时间复杂度为 $O(n)$。
• 故总时间复杂度为 $O(m + n)$。

空间复杂度

• 需要 $O(m)$ 的额外空间存储素数数组。

C++ 代码

const int N = 101;

vector<int> primes;
bool not_prime[N];

auto init = [] {
    not_prime[1] = true;

    for (int i = 2; i < N; i++) {
        if (!not_prime[i])
            primes.push_back(i);

        for (int j = 0; j < primes.size() && i * primes[j] <= N; j++) {
            not_prime[i * primes[j]] = true;
            if (i % primes[j] == 0)
                break;
        }
    }

    return 0;
}();

class Solution {
public:
    int maximumPrimeDifference(vector<int>& nums) {
        const int n = nums.size();

        int i, j;
        for (i = 0; i < n && not_prime[nums[i]]; i++);
        for (j = n - 1; j >= 0 && not_prime[nums[j]]; j--);

        return j - i;
    }
};