Sự khác biệt giữa số nguyên tố lớn nhất và nhỏ nhất trong một mảng trong Java

Tuyên bố vấn đề

Với một mảng số nguyên đã cho trong đó tất cả các phần tử nhỏ hơn 1000000. Tìm hiệu số giữa số nguyên tố lớn nhất và nhỏ nhất trong một mảng.

Ví dụ

Array: [ 1, 2, 3, 4, 5 ]

Largest Prime Number = 5
Smallest Prime Number = 2

Difference = 5 - 3 = 2.

Giải pháp

Sử dụng phương pháp tiếp cận Sieve of Eratosthenes, đây là một cách hiệu quả để tìm ra tất cả các số nguyên tố nhỏ hơn một số nhất định. Sau đó, chúng tôi sẽ tìm ra số nguyên tố lớn nhất và nhỏ nhất để nhận được sự khác biệt cần thiết.

Ví dụ

Sau đây là chương trình trong Java để tìm đầu ra cần thiết.

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));
   }
}

Đầu ra

3