Java数组中最大质数和最小质数之间的差异
问题陈述
对于给定的整数数组，其中所有元素均小于1000000。找到数组中最大素数和最小素数之间的差。
示例
Array: [ 1, 2, 3, 4, 5 ] Largest Prime Number = 5 Smallest Prime Number = 2 Difference = 5 - 3 = 2.
解
使用Eratosthenes筛分法，这是找出小于给定数的所有素数的有效方法。然后，我们将找出最大和最小的质数以获得所需的差。
示例
以下是Java中的程序，用于查找所需的输出。
public class JavaTester {
static int MAX = 1000000;
static boolean prime[] = new boolean[MAX + 1];
public static void runSieveOfEratosthenes(){
//将质数标志重置为true-
for(int i=0; i< MAX+1; i++) prime[i] = true;
//将1设置为非素数
prime[1] = false;
for (int p = 2; p * p <= MAX; p++) {
//如果prime[p]没有被修改，那么它是一个质数
if (prime[p]) {
//更新p的所有倍数
for (int i = p * 2; i <= MAX; i += p) prime[i] = false;
}
}
}
public static int difference(int arr[]){
int min = MAX + 2;
int max = -1;
for (int i = 0; i < arr.length; i++) {
//检查数字是否为素数
if (prime[arr[i]] == true) {
//设置最大值和最小值
if (arr[i] > max) max = arr[i];
if (arr[i] < min) min = arr[i];
}
}
return max - min;
}
public static void main(String args[]){
//筛
runSieveOfEratosthenes();
int arr[] = { 1, 2, 3, 4, 5 };
System.out.println(difference(arr));
}
}输出结果
3