ความแตกต่างระหว่างจำนวนเฉพาะที่มากที่สุดและน้อยที่สุดในอาร์เรย์ด้วย Java

โจทย์

ได้รับอาร์เรย์ของจำนวนเต็มที่ทุกตัวมีค่าน้อยกว่า 1,000,000 ให้หาความต่างระหว่างจำนวนเฉพาะที่มากที่สุดและน้อยที่สุดในอาร์เรย์

ตัวอย่าง

Array: [ 1, 2, 3, 4, 5 ]
Largest Prime Number = 5
Smallest Prime Number = 2
Difference = 5 - 2 = 3

วิธีแก้

ใช้วิธี Sieve of Eratosthenes ซึ่งเป็นวิธีที่มีประสิทธิภาพในการหาจำนวนเฉพาะทั้งหมดที่น้อยกว่าตัวเลขที่กำหนด จากนั้นหาจำนวนเฉพาะที่มากที่สุดและน้อยที่สุดเพื่อคำนวณความต่าง

ตัวอย่างโค้ด Java

public class JavaTester {
    static int MAX = 1000000;
    static boolean prime[] = new boolean[MAX + 1];

    public static void runSieveOfEratosthenes(){
        // รีเซ็ตค่า prime flags เป็น true
        for(int i=0; i < MAX+1; i++) prime[i] = true;
        // ตั้งค่า 1 เป็น non-prime
        prime[1] = false;
        for (int p = 2; p * p <= MAX; p++) {
            // ถ้า prime[p] ไม่ถูกแก้ไข แสดงว่าเป็นจำนวนเฉพาะ
            if (prime[p]) {
                // อัปเดตทุกตัวคูณของ 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++) {
            // ตรวจสอบว่าเลขนั้นเป็นเฉพาะหรือไม่
            if (prime[arr[i]] == true) {
                // ตั้งค่า max และ min
                if (arr[i] > max) max = arr[i];
                if (arr[i] < min) min = arr[i];
            }
        }
        return max - min;
    }

    public static void main(String args[]){
        // รัน sieve
        runSieveOfEratosthenes();
        int arr[] = { 1, 2, 3, 4, 5 };
        System.out.println(difference(arr));
    }
}

ผลลัพธ์

3