मान लीजिए हमारे पास एक संख्या n है। हमें सबसे बड़ा विशेष अभाज्य संख्या ढूंढनी है जो N से कम या बराबर हो। विशेष अभाज्य संख्या एक ऐसी संख्या है, जिसे एक के बाद एक अंक रखकर बनाया जा सकता है, ताकि सभी परिणामस्वरूप संख्याएं अभाज्य हों।
यहां हम एराटोस्थनीज की छलनी का उपयोग करेंगे। हम संख्या 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
