Java의 배열에서 가장 큰 소수와 가장 작은 소수의 차이점

문제 설명

모든 요소가 1000000보다 작은 주어진 정수 배열로 배열에서 가장 큰 소수와 가장 작은 소수의 차이를 찾으십시오.

예

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

Largest Prime Number = 5
Smallest Prime Number = 2

Difference = 5 - 3 = 2.

해결책

주어진 수보다 작은 모든 소수를 찾는 효율적인 방법인 에라토스테네스의 체 접근법을 사용합니다. 그런 다음 필요한 차이를 얻기 위해 가장 큰 소수와 가장 작은 소수를 알아낼 것입니다.

예

다음은 필요한 출력을 찾는 Java 프로그램입니다.

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