数据结构
网络
关系型数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学在C++中查找数组中满足(A[i] % K)最大的素数K
假设我们有一个包含n个整数的数组A。我们必须找到一个元素K，使得K是素数，并且对于所有有效的i，A[i] mod K在所有可能的K值中最大。如果没有找到这样的数字，则返回-1。例如，如果A = [2, 10, 15, 7, 6, 8, 13]，则输出将为13。有三个素数2、7和13。A[i] mod 2的最大可能值为1（15 mod 2），对于7，它将为6 mod 7 = 6，而对于13，它将为10 mod 13 = 10。这是最大值。
为了最大化A[i] mod K的值，K必须是A中的最大素数，而A[i]必须是小于K的数组中最大的元素。因此，我们将只找到数组中的最大素数。为了做到这一点，我们可以使用筛法找到小于或等于数组中最大元素的所有素数。然后找到数组中的最大素数并打印出来。如果没有素数，则返回-1。
示例
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int getMaxPrime(int arr[], int n) {
int max_elem = *max_element(arr, arr + n);
vector<bool> prime_vals(max_elem + 1, true);
prime_vals[0] = false;
prime_vals[1] = false;
for (int p = 2; p * p <= max_elem; p++) {
if (prime_vals[p] == true) {
for (int i = p * 2; i <= max_elem; i += p)
prime_vals[i] = false;
}
}
int maximum = -1;
for (int i = 0; i < n; i++) {
if (prime_vals[arr[i]])
maximum = max(maximum, arr[i]);
}
return maximum;
}
int main() {
int arr[] = { 2, 10, 15, 7, 6, 8, 13 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Max prime is: " << getMaxPrime(arr, n);
}输出
Max prime is: 13
更新于：2019年12月18日
80 次查看
广告