資料結構
網路
關係資料庫管理系統
作業系統
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 次檢視
廣告