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