数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究Java数组中最大和最小素数的差
问题陈述
给定一个整数数组，其中所有元素都小于 1000000。找到数组中最大和最小素数之间的差。
示例
Array: [ 1, 2, 3, 4, 5 ] Largest Prime Number = 5 Smallest Prime Number = 2 Difference = 5 - 3 = 2.
解决方案
使用埃拉托色尼筛法，这是一种有效找出小于给定数字的所有素数的方法。然后我们将找出最大和最小的素数以获得所需的差值。
示例
以下是 Java 程序，用于查找所需输出。
public class JavaTester {
static int MAX = 1000000;
static boolean prime[] = new boolean[MAX + 1];
public static void runSieveOfEratosthenes(){
//reset prime flags to be true
for(int i=0; i< MAX+1; i++) prime[i] = true;
//set 1 as non-prime
prime[1] = false;
for (int p = 2; p * p <= MAX; p++) {
// If prime[p] is not modified, then it is a prime
if (prime[p]) {
// Update all multiples of 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++) {
// check if the number is prime or not
if (prime[arr[i]] == true) {
// set the max and min values
if (arr[i] > max) max = arr[i];
if (arr[i] < min) min = arr[i];
}
}
return max - min;
}
public static void main(String args[]){
// run the sieve
runSieveOfEratosthenes();
int arr[] = { 1, 2, 3, 4, 5 };
System.out.println(difference(arr));
}
}输出
3
更新于: 2020年5月16日
828 次查看
广告