สมมติว่าเรามีตัวเลข n เราต้องหาจำนวนเฉพาะพิเศษที่ใหญ่ที่สุดซึ่งน้อยกว่าหรือเท่ากับ N จำนวนเฉพาะพิเศษคือตัวเลข ซึ่งสามารถสร้างขึ้นได้โดยการวางตัวเลขทีละตัว ดังนั้นจำนวนผลลัพธ์ทั้งหมดจึงเป็นจำนวนเฉพาะ
เราจะใช้ Sieve Of Eratosthenes เราจะสร้างอาร์เรย์ตะแกรงจนถึงจำนวน n จากนั้นเริ่มวนซ้ำจากตัวเลข N โดยตรวจสอบว่าตัวเลขนั้นเป็นจำนวนเฉพาะหรือไม่ เมื่อเป็นจำนวนเฉพาะ ให้ตรวจสอบว่านี่เป็นจำนวนเฉพาะพิเศษหรือไม่
ตัวอย่าง
#include<iostream>
using namespace std;
bool isSpecialPrime(bool sieve[], int num) {
while (num) {
if (!sieve[num]) {
return false;
}
num /= 10;
}
return true;
}
void findSpecialPrime(int N) {
bool sieve[N + 10];
for(int i = 0; i<N+10; i++){
sieve[i] = true;
}
sieve[0] = sieve[1] = false;
for (long long i = 2; i <= N; i++) {
if (sieve[i]) {
for (long long j = i * i; j <= N; j += i) {
sieve[j] = false;
}
}
}
while (true) {
if (isSpecialPrime(sieve, N)) {
cout << N << '\n';
break;
}
else
N--;
}
}
int main() {
cout << "Special prime in range (2 -> 400): ";
findSpecialPrime(400);
cout << "Special prime in range (2 -> 100): ";
findSpecialPrime(100);
} ผลลัพธ์
Special prime in range (2 -> 400): 379 Special prime in range (2 -> 100): 79
