समस्या का विवरण
पूर्णांकों की दी गई सरणी के साथ जहां सभी तत्व 1000000 से कम हैं। किसी सरणी में सबसे बड़े और सबसे छोटे अभाज्य संख्याओं के बीच अंतर ज्ञात करें।
उदाहरण
Array: [ 1, 2, 3, 4, 5 ] Largest Prime Number = 5 Smallest Prime Number = 2 Difference = 5 - 3 = 2.
समाधान
एराटोस्थनीज की चलनी का उपयोग करें, जो एक दी गई संख्या से छोटी सभी अभाज्य संख्याओं का पता लगाने का एक प्रभावी तरीका है। फिर हम आवश्यक अंतर प्राप्त करने के लिए सबसे बड़ी और सबसे छोटी अभाज्य संख्या का पता लगाएंगे।
उदाहरण
आवश्यक आउटपुट खोजने के लिए जावा में प्रोग्राम निम्नलिखित है।
public class JavaTester {
static int MAX = 1000000;
static boolean prime[] = new boolean[MAX + 1];
public static void runSieveOfEratosthenes(){
//reset prime flags to be true
for(int i=0; i< MAX+1; i++) prime[i] = true;
//set 1 as non-prime
prime[1] = false;
for (int p = 2; p * p <= MAX; p++) {
// If prime[p] is not modified, then it is a prime
if (prime[p]) {
// Update all multiples of p
for (int i = p * 2; i <= MAX; i += p) prime[i] = false;
}
}
}
public static int difference(int arr[]){
int min = MAX + 2;
int max = -1;
for (int i = 0; i < arr.length; i++) {
// check if the number is prime or not
if (prime[arr[i]] == true) {
// set the max and min values
if (arr[i] > max) max = arr[i];
if (arr[i] < min) min = arr[i];
}
}
return max - min;
}
public static void main(String args[]){
// run the sieve
runSieveOfEratosthenes();
int arr[] = { 1, 2, 3, 4, 5 };
System.out.println(difference(arr));
}
} आउटपुट
3
