สมมติว่ามีอาร์เรย์ 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
