समस्या कथन
n धनात्मक पूर्णांकों की एक सरणी दी गई है। हमें न्यूनतम और अधिकतम मान वाली अभाज्य संख्या ढूंढनी है।
यदि सरणी है: arr[] = {10, 4, 1, 12, 13, 7, 6, 2, 27, 33} तो न्यूनतम अभाज्य संख्या 2 है और अधिकतम अभाज्य संख्या 13 है।
एल्गोरिदम
- दिए गए सरणी से अधिकतम संख्या ढूंढें। इसे maxNumber कहें।
- 1 से maxNumber तक अभाज्य संख्याएं उत्पन्न करें और उन्हें एक डायनामिक सरणी में संग्रहीत करें (Sieve of Eratosthenes)।
- इनपुट सरणी पर पुनरावृति करें और डायनामिक सरणी का उपयोग करके न्यूनतम और अधिकतम मान वाली अभाज्य संख्या ढूंढें।
C++ कोड उदाहरण
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
void printMinAndMaxPrimes(int *arr, int n) {
int maxNumber = *max_element(arr, arr + n);
vector primes(maxNumber + 1, true);
primes[0] = primes[1] = false;
for(int p = 2; p * p <= maxNumber; ++p) {
if(primes[p]) {
for(int i = p * 2; i <= maxNumber; i += p)
primes[i] = false;
}
}
int minPrime = INT_MAX;
int maxPrime = INT_MIN;
for(int i = 0; i < n; ++i) {
if(primes[arr[i]]) {
minPrime = min(minPrime, arr[i]);
maxPrime = max(maxPrime, arr[i]);
}
}
cout << "Prime number of min value = " << minPrime << "\n";
cout << "Prime number of max value = " << maxPrime << "\n";
}
int main() {
int arr[] = {10, 4, 1, 12, 13, 7, 6, 2, 27, 33};
printMinAndMaxPrimes(arr, SIZE(arr));
return 0;
} आउटपुट
Prime number of min value = 2 Prime number of max value = 13
