目标
给你一个整数数组 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^5
- 1 <= nums[i] <= 100
- 输入保证 nums 中至少有一个质数。
思路
找出数组中质数的最远距离（下标之差）。
知识点：
- 自然数：非负整数
- 质数：只能被1和它本身整除的大于1的自然数
- 合数：不是质数的大于1的自然数
如果 n 是一个合数，那么它可以分解为两个自然数 a、b 的乘积，即 n = a * b。设 a ≤ b ，如果 a ≥ √n ，那么 a * b ≥ n。 也就是说 a、b 要么同时等于 √n，要么一个大于一个小于 √n，不可能同时大于√n。于是判断一个数是否是质数，只需判断 n 是否能够整除 1 ~ √n 。
除了2的偶数都不是质数，因此自增的步长可以设为2。
更进一步分析，所有质数除了2和3外，都形如 6k - 1 或 6k + 1。考虑 n % 6 ：
- 余数为0，首先6不是质数，能被6整除的数也不是质数
- 余数为2、4，表明能够被2整除，不是质数
- 余数为3，表明能被3整除，不是质数
- 余数为5，
6k - 1 - 余数为1，
6k + 1
从5开始，步长可以设为6。
代码
/**
* @date 2024-07-02 9:13
*/
public class MaximumPrimeDifference3115 {
public int maximumPrimeDifference_v2(int[] nums) {
int i = 0, j = nums.length - 1;
while (!isPrimeNumber(nums[i])) {
i++;
}
while (!isPrimeNumber(nums[j])) {
j--;
}
return j - i;
}
public boolean isPrimeNumber(int num) {
if (num == 1) {
return false;
}
if (num == 2) {
return true;
}
if (num % 2 == 0) {
return false;
}
for (int i = 3; i * i <= num; i += 2) {
if (num % i == 0) {
return false;
}
}
return true;
}
public static boolean isPrimeNumber_v1(int num) {
if (num <= 1) {
return false;
}
if (num <= 3) {
return true;
}
if (num % 2 == 0 || num % 3 == 0) {
return false;
}
for (int i = 5; i * i <= num; i += 6) {
// i = 6k - 1, i + 2 = 6k + 1
if (num % i == 0 || num % (i + 2) == 0) {
return false;
}
}
return true;
}
}
性能
