Cho mảng A n phần tử, tìm K là số nguyên tố trong mảng sao cho max(A[i] % K) là lớn nhất. Ví dụ A=[2,10,15,7,6,8,13] → K=13 (vì 10%13=10 lớn nhất).
Để tối đa A[i]%K, K nên là số nguyên tố lớn nhất trong mảng, và A[i] là phần tử lớn nhất nhỏ hơn K. Dùng sàng tìm số nguyên tố ≤ max phần tử, sau đó lấy số nguyên tố lớn nhất trong mảng.
Ví dụ
#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); }
Kết quả
Max prime is: 13