สมมติว่าเรามีอาร์เรย์ A ที่มีจำนวนเต็ม n เราต้องหาองค์ประกอบ K หนึ่งตัวเพื่อให้ K เป็นจำนวนเฉพาะ และ A[i] mod K เป็นค่าสูงสุดสำหรับค่า i ที่ถูกต้องทั้งหมดจากค่าที่เป็นไปได้ทั้งหมดของ K หากไม่พบตัวเลขดังกล่าว ให้คืนค่า -1 ตัวอย่างเช่น ถ้า A =[2, 10, 15, 7, 6, 8, 13] ผลลัพธ์จะเป็น 13 มีตัวเลขเฉพาะ 3 จำนวน 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
