数据结构
网络
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 次浏览
广告