素数的最大距离

100265. 素数的最大距离

给你一个整数数组 nums。

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

示例 1：

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

输出： 3

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

示例 2：

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

输出： 0

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

提示：

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

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int maximumPrimeDifference(vector<int>& nums) { } };

rust 解法, 执行用时: 22 ms, 内存消耗: 4 MB, 提交时间: 2024-07-02 09:32:09

use std::collections::HashSet;

impl Solution {
    pub fn maximum_prime_difference(nums: Vec<i32>) -> i32 {
        let primes: HashSet<i32> = [
            2, 3, 5, 7, 11,
            13, 17, 19, 23, 29,
            31, 37, 41, 43, 47,
            53, 59, 61, 67, 71,
            73, 79, 83, 89, 97
        ].iter().cloned().collect();

        let mut first = -1;
        let mut ans = 0;

        for (i, &num) in nums.iter().enumerate() {
            if primes.contains(&num) {
                if first != -1 {
                    ans = ans.max(i as i32 - first);
                } else {
                    first = i as i32;
                }
            }
        }
        ans
    }
}

javascript 解法, 执行用时: 96 ms, 内存消耗: 64.7 MB, 提交时间: 2024-07-02 09:31:54

/**
 * @param {number[]} nums
 * @return {number}
 */
var maximumPrimeDifference = function(nums) {
    const primes = new Set([
        2, 3, 5, 7, 11,
        13, 17, 19, 23, 29,
        31, 37, 41, 43, 47,
        53, 59, 61, 67, 71,
        73, 79, 83, 89, 97
    ]);

    const n = nums.length;
    let first = -1, ans = 0;
    for (let i = 0; i < n; ++i) {
        if (primes.has(nums[i])) {
            if (first !== -1) {
                ans = Math.max(ans, i - first);
            } else {
                first = i;
            }
        }
    }
    return ans;
};

golang 解法, 执行用时: 93 ms, 内存消耗: 14.7 MB, 提交时间: 2024-04-15 14:19:02

const mx = 101
var notPrime = [mx]bool{true, true}
func init() {
	for i := 2; i*i < mx; i++ {
		if !notPrime[i] {
			for j := i * i; j < mx; j += i {
				notPrime[j] = true // j 是质数 i 的倍数
			}
		}
	}
}

// 预处理
func maximumPrimeDifference(nums []int) int {
	i := 0
	for notPrime[nums[i]] {
		i++
	}
	j := len(nums) - 1
	for notPrime[nums[j]] {
		j--
	}
	return j - i
}

func isPrime(n int) bool {
	for i := 2; i*i <= n; i++ {
		if n%i == 0 {
			return false
		}
	}
	return n >= 2
}

func maximumPrimeDifference2(nums []int) int {
	i := 0
	for !isPrime(nums[i]) {
		i++
	}
	j := len(nums)-1
	for !isPrime(nums[j]) {
		j--
	}
	return j - i
}

cpp 解法, 执行用时: 109 ms, 内存消耗: 104.5 MB, 提交时间: 2024-04-15 14:18:22

// 预处理
const int MX = 101;
bool not_prime[MX];

auto init = [] {
    not_prime[1] = true;
    for (int i = 2; i * i < MX; i++) {
        if (not_prime[i]) continue;
        for (int j = i * i; j < MX; j += i) {
            not_prime[j] = true; // j 是质数 i 的倍数
        }
    }
    return 0;
}();

class Solution {
    bool is_prime(int n) {
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return n >= 2;
    }

public:
    int maximumPrimeDifference2(vector<int>& nums) {
        int i = 0;
        while (!is_prime(nums[i])) {
            i++;
        }
        int j = nums.size() - 1;
        while (!is_prime(nums[j])) {
            j--;
        }
        return j - i;
    }
    
    // 预处理
    int maximumPrimeDifference(vector<int>& nums) {
        int i = 0;
        while (not_prime[nums[i]]) {
            i++;
        }
        int j = nums.size() - 1;
        while (not_prime[nums[j]]) {
            j--;
        }
        return j - i;
    }
};

java 解法, 执行用时: 0 ms, 内存消耗: 77.7 MB, 提交时间: 2024-04-15 14:16:58

class Solution {
    private static final int MX = 101;
    private static final boolean[] NOT_PRIME = new boolean[MX];

    static {
        NOT_PRIME[1] = true;
        for (int i = 2; i * i < MX; i++) {
            if (NOT_PRIME[i]) continue;
            for (int j = i * i; j < MX; j += i) {
                NOT_PRIME[j] = true; // j 是质数 i 的倍数
            }
        }
    }

    public int maximumPrimeDifference(int[] nums) {
        int i = 0;
        while (NOT_PRIME[nums[i]]) {
            i++;
        }
        int j = nums.length - 1;
        while (NOT_PRIME[nums[j]]) {
            j--;
        }
        return j - i;
    }


    public int maximumPrimeDifference2(int[] nums) {
        int i = 0;
        while (!isPrime(nums[i])) {
            i++;
        }
        int j = nums.length - 1;
        while (!isPrime(nums[j])) {
            j--;
        }
        return j - i;
    }

    private boolean isPrime(int n) {
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return n >= 2;
    }
}

python3 解法, 执行用时: 61 ms, 内存消耗: 28.5 MB, 提交时间: 2024-04-15 14:16:15

MX = 101
not_prime = [True, True] + [False] * (MX - 2)
for i in range(2, isqrt(MX) + 1):
    if not_prime[i]: continue
    for j in range(i * i, MX, i):
        not_prime[j] = True  # j 是质数 i 的倍数

class Solution:
    def maximumPrimeDifference(self, nums: List[int]) -> int:
        i = 0
        while not_prime[nums[i]]:
            i += 1
        j = len(nums) - 1
        while not_prime[nums[j]]:
            j -= 1
        return j - i

python3 解法, 执行用时: 46 ms, 内存消耗: 28.5 MB, 提交时间: 2024-04-15 14:15:27

# 预处理
not_prime = [False] * 101
not_prime[1] = True
for i in 2, 3, 5, 7:
    for j in range(i * i, 101, i):
        not_prime[j] = True

class Solution:
    def maximumPrimeDifference(self, nums: List[int]) -> int:
        i = 0
        while not_prime[nums[i]]:
            i += 1
        j = len(nums) - 1
        while not_prime[nums[j]]:
            j -= 1
        return j - i
        
    def maximumPrimeDifference2(self, nums: List[int]) -> int:
        is_prime = lambda n: n >= 2 and all(n % i for i in range(2, isqrt(n) + 1))
        i = 0
        while not is_prime(nums[i]):
            i += 1
        j = len(nums) - 1
        while not is_prime(nums[j]):
            j -= 1
        return j - i

上一题

下一题

详情