Chênh lệch giữa số nguyên tố lớn nhất và nhỏ nhất trong mảng trong Java

Đề bài

Cho một mảng các số nguyên với tất cả các phần tử nhỏ hơn 1.000.000. Tìm chênh lệch giữa số nguyên tố lớn nhất và nhỏ nhất trong mảng.

Ví dụ

Mảng: [ 1, 2, 3, 4, 5 ] 
Số nguyên tố lớn nhất = 5 
Số nguyên tố nhỏ nhất = 2 
Chênh lệch = 5 - 2 = 3.

Giải pháp

Sử dụng phương pháp Sàng Eratosthenes, một cách hiệu quả để tìm tất cả các số nguyên tố nhỏ hơn một số cho trước. Sau đó xác định số nguyên tố lớn nhất và nhỏ nhất để tính chênh lệch.

Ví dụ

Chương trình Java sau tìm kết quả yêu cầu.

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

Kết quả

3