n개의 정수가 있는 배열 A가 있다고 가정합니다. K가 소수이고 A[i] mod K가 K의 가능한 모든 값 중에서 모든 유효한 i에 대해 최대인 하나의 요소 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보다 작은 배열에서 가장 큰 요소여야 합니다. 따라서 우리는 최대 소수를 찾을 것입니다. 배열. 이를 얻기 위해 Sieve를 사용하여 배열의 최대 요소보다 작거나 같은 모든 소수를 찾을 수 있습니다. 그런 다음 배열에서 최대 소수를 찾아 인쇄합니다. 소수가 없으면 -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