資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究查詢最大素數差值程式
最大素數差值問題用於確定給定陣列中兩個素數索引之間的最大差值。
問題陳述
在這裡，我們給定一個整數陣列 nums。我們的任務是在陣列中找到任意兩個素數索引之間的最大素數差值。
如果給定陣列中只有一個素數，則返回 0；如果沒有素數，則返回 -1。
示例場景 1
Input: arr = [11, 4, 7, 6, 13]
Output: 4
素數為 11（索引 0）、7（索引 2）和 13（索引 4）。它們索引之間的最大差值為 |4 - 0| = 4。
示例場景 2
Input: arr = [8, 10, 15, 20]
Output: -1
沒有素數。因此輸出為 -1。
示例場景 3
Input: arr = [8, 17, 6, 23, 5, 29, 31]
Output: 5
素數為 17（索引 1）、23（索引 3）、5（索引 4）、29（索引 5）和 31（索引 6）。它們索引之間的最大差值為 |6 - 1| = 5。
示例場景 4
Input: arr = [4, 6, 8, 10, 13]
Output: 0
在此示例中，只有一個素數 13（索引 4），它們索引之間的最大差值為 |4 - 4| = 0。
為了用各種程式語言解決此問題，這裡有兩種重要的方法。
- 篩法掃描
- 雙指標素數檢查
篩法掃描
示例
我們使用此方法查詢陣列中最大值之前的全部素數。然後，我們遍歷陣列以查詢這些素數的索引，並計算它們之間的最大差值。時間複雜度為 O(n \log \log n) + O(m)。其中 n 為長度，m 為陣列中的最大值。
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
vector<bool> sieve(int max_val) {
vector<bool> is_prime(max_val + 1, true);
is_prime[0] = is_prime[1] = false;
for (int i = 2; i <= sqrt(max_val); ++i) {
if (is_prime[i]) {
for (int j = i * i; j <= max_val; j += i) {
is_prime[j] = false;
}
}
}
return is_prime;
}
int maxPrimeDifference(const vector<int>& arr) {
int max_val = *max_element(arr.begin(), arr.end());
vector<bool> is_prime = sieve(max_val);
vector<int> prime_indices;
for (int i = 0; i < arr.size(); ++i) {
if (is_prime[arr[i]]) {
prime_indices.push_back(i);
}
}
if (prime_indices.size() < 2) return -1;
return prime_indices.back() - prime_indices.front();
}
int main() {
vector<int> arr = {8, 17, 6, 23, 5, 29, 31};
cout << "Maximum Prime Difference = " << maxPrimeDifference(arr) << endl;
return 0;
}
輸出
Maximum Prime Difference = 5
import java.util.*;
public class MaxPrimeDifference {
public static boolean[] sieve(int maxVal) {
boolean[] isPrime = new boolean[maxVal + 1];
Arrays.fill(isPrime, true);
isPrime[0] = isPrime[1] = false;
for (int i = 2; i <= Math.sqrt(maxVal); i++) {
if (isPrime[i]) {
for (int j = i * i; j <= maxVal; j += i) {
isPrime[j] = false;
}
}
}
return isPrime;
}
public static int maxPrimeDifference(int[] arr) {
int maxVal = Arrays.stream(arr).max().getAsInt();
boolean[] isPrime = sieve(maxVal);
List<Integer> primeIndices = new ArrayList<>();
for (int i = 0; i < arr.length; i++) {
if (isPrime[arr[i]]) {
primeIndices.add(i);
}
}
if (primeIndices.size() < 2) return -1;
return primeIndices.get(primeIndices.size() - 1) - primeIndices.get(0);
}
public static void main(String[] args) {
int[] arr = {8, 17, 6, 23, 5, 29, 31};
System.out.println("Maximum Prime Difference = " + maxPrimeDifference(arr));
}
}
輸出
Maximum Prime Difference = 5
def sieve(max_val):
is_prime = [True] * (max_val + 1)
is_prime[0] = is_prime[1] = False
for i in range(2, int(max_val**0.5) + 1):
if is_prime[i]:
for j in range(i * i, max_val + 1, i):
is_prime[j] = False
return is_prime
def max_prime_difference(arr):
max_val = max(arr)
is_prime = sieve(max_val)
prime_indices = [i for i, num in enumerate(arr) if is_prime[num]]
if len(prime_indices) < 2:
return -1
return prime_indices[-1] - prime_indices[0]
arr = [8, 17, 6, 23, 5, 29, 31]
print("Maximum Prime Difference = ", max_prime_difference(arr))
輸出
Maximum Prime Difference = 5
package main
import (
"fmt"
"math"
)
func sieve(maxVal int) []bool {
isPrime := make([]bool, maxVal+1)
for i := 2; i <= maxVal; i++ {
isPrime[i] = true
}
for i := 2; i <= int(math.Sqrt(float64(maxVal))); i++ {
if isPrime[i] {
for j := i * i; j <= maxVal; j += i {
isPrime[j] = false
}
}
}
return isPrime
}
func maxPrimeDifference(arr []int) int {
maxVal := 0
for _, num := range arr {
if num > maxVal {
maxVal = num
}
}
isPrime := sieve(maxVal)
primeIndices := []int{}
for i, num := range arr {
if isPrime[num] {
primeIndices = append(primeIndices, i)
}
}
if len(primeIndices) < 2 {
return -1
}
return primeIndices[len(primeIndices)-1] - primeIndices[0]
}
func main() {
arr := []int{8, 17, 6, 23, 5, 29, 31}
fmt.Println("Maximum Prime Difference = ", maxPrimeDifference(arr))
}
輸出
Maximum Prime Difference = 5
雙指標素數檢查
示例
要查詢最大素數差值，您可以使用直接素數檢查函式來識別陣列中的素數。然後，使用兩個指標跟蹤這些素數的第一次和最後一次出現。最後，計算它們索引之間的差值。此方法的時間複雜度為 O(m\sqrt{k})，其中 (m) 為陣列的長度，(k) 為陣列中元素的平均值。
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
bool isPrime(int num) {
if (num <= 1) return false;
for (int i = 2; i <= sqrt(num); ++i) {
if (num % i == 0) return false;
}
return true;
}
int maxPrimeDifference(const vector<int>& arr) {
int first = -1, last = -1;
for (int i = 0; i < arr.size(); ++i) {
if (isPrime(arr[i])) {
if (first == -1) first = i;
last = i;
}
}
if (first == -1 || last == -1 || first == last) return -1;
return last - first;
}
int main() {
vector<int> arr = {8, 17, 6, 23, 5, 29, 31};
cout << "Maximum Prime Difference = " << maxPrimeDifference(arr) << endl;
return 0;
}
輸出
Maximum Prime Difference = 5
public class MaxPrimeDifference {
public static boolean isPrime(int num) {
if (num <= 1) return false;
for (int i = 2; i <= Math.sqrt(num); i++) {
if (num % i == 0) return false;
}
return true;
}
public static int maxPrimeDifference(int[] arr) {
int first = -1, last = -1;
for (int i = 0; i < arr.length; i++) {
if (isPrime(arr[i])) {
if (first == -1) first = i;
last = i;
}
}
if (first == -1 || last == -1 || first == last) return -1;
return last - first;
}
public static void main(String[] args) {
int[] arr = {8, 17, 6, 23, 5, 29, 31};
System.out.println("Maximum Prime Difference = " + maxPrimeDifference(arr));
}
}
輸出
Maximum Prime Difference = 5
import math
def is_prime(num):
if num <= 1:
return False
for i in range(2, int(math.sqrt(num)) + 1):
if num % i == 0:
return False
return True
def max_prime_difference(arr):
first = last = -1
for i, num in enumerate(arr):
if is_prime(num):
if first == -1:
first = i
last = i
if first == -1 or last == -1 or first == last:
return -1
return last - first
arr = [8, 17, 6, 23, 5, 29, 31]
print("Maximum Prime Difference = ", max_prime_difference(arr))
輸出
Maximum Prime Difference = 5
package main
import (
"fmt"
"math"
)
func isPrime(num int) bool {
if num <= 1 {
return false
}
for i := 2; i <= int(math.Sqrt(float64(num))); i++ {
if num%i == 0 {
return false
}
}
return true
}
func maxPrimeDifference(arr []int) int {
first, last := -1, -1
for i, num := range arr {
if isPrime(num) {
if first == -1 {
first = i
}
last = i
}
}
if first == -1 || last == -1 || first == last {
return -1
}
return last - first
}
func main() {
arr := []int{8, 17, 6, 23, 5, 29, 31}
fmt.Println("Maximum Prime Difference = ", maxPrimeDifference(arr))
}
輸出
Maximum Prime Difference = 5
更新於: 2024年7月23日
71 次瀏覽
廣告