Skip to Content
CoursesCSC102การหาระยะห่างน้อยสุดระหว่างค่าของจำนวนเฉพาะ

DIY

โจทย์

You will receive an array of 20 integers, and you must identify all pairs of distinct prime numbers and calculate the distance between each pair. The distance is defined as the absolute difference between the two prime numbers. Your task is to find and print the minimum distance among all possible pairs of prime numbers found in the array. If there is no prime number pair in the list, print “No prime pair was found”.

Note: The input number shall not exceed 100.

InputOutput
29 1 17 5 12 19 70 80 90 100 15 25 35 45 55 65 75 85 95 152
10 20 30 40 50 60 70 80 90 100 15 25 35 45 55 65 75 85 95 15No prime pair was found.

โค้ด

import java.util.Scanner;
 
public class Program {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
 
        int[] numbers = new int[20];
        boolean[] isPrime = new boolean[20];
 
        for (int i = 0; i < isPrime.length; i++) {
            int number = scanner.nextInt();
            numbers[i] = number;
            isPrime[i] = isPrime(number);
        }
 
        int minDistance = Integer.MAX_VALUE;
        boolean foundPrimePair = false;
 
        for (int i = 0; i < isPrime.length; i++) {
            if (isPrime[i]) {
                for (int j = i + 1; j < isPrime.length; j++) {
                    if (isPrime[j]) {
                        int distance = Math.abs(numbers[i] - numbers[j]);
                        minDistance = Math.min(minDistance, distance);
                        foundPrimePair = true;
                    }
                }
            }
        }
 
        if (foundPrimePair) {
            System.out.println(minDistance);
        } else {
            System.out.println("No prime pair was found.");
        }
 
    }
 
    private static boolean isPrime(int number) {
        if (number <= 1) return false;
        if (number <= 3) return true;
        if (number % 2 == 0 || number % 3 == 0) return false;
 
        for (int i = 5; i * i <= number; i += 6) {
            if (number % i == 0 || number % (i + 2) == 0) {
                return false;
            }
        }
        return true;
    }
}

คำอธิบาย

1. การรับข้อมูลและตรวจสอบจำนวนเฉพาะ

int[] numbers = new int[20];         // เก็บตัวเลขที่รับเข้ามา
boolean[] isPrime = new boolean[20]; // เก็บสถานะว่าเป็นจำนวนเฉพาะหรือไม่
 
for (int i = 0; i < isPrime.length; i++) {
    int number = scanner.nextInt();
    numbers[i] = number;
    isPrime[i] = isPrime(number);    // ตรวจสอบและเก็บสถานะจำนวนเฉพาะ
}

2. การตรวจสอบจำนวนเฉพาะ

private static boolean isPrime(int number) {
    if (number <= 1) return false;
    if (number <= 3) return true;
    if (number % 2 == 0 || number % 3 == 0) return false;
 
    for (int i = 5; i * i <= number; i += 6) {
        if (number % i == 0 || number % (i + 2) == 0) {
            return false;
        }
    }
    return true;
}

วิธีการตรวจสอบจำนวนเฉพาะที่มีประสิทธิภาพ

  1. ตรวจสอบกรณีพิเศษ (≤ 1, 2, 3)
  2. ตรวจสอบการหารด้วย 2 และ 3
  3. ตรวจสอบตัวหารที่เหลือในรูปแบบ 6k ± 1

3. การหาระยะห่างน้อยสุด

int minDistance = Integer.MAX_VALUE;
boolean foundPrimePair = false;
 
for (int i = 0; i < isPrime.length; i++) {
    if (isPrime[i]) {                           // ถ้าพบจำนวนเฉพาะตัวแรก
        for (int j = i + 1; j < isPrime.length; j++) {
            if (isPrime[j]) {                   // ถ้าพบจำนวนเฉพาะตัวที่สอง
                int distance = Math.abs(numbers[i] - numbers[j]);
                minDistance = Math.min(minDistance, distance);
                foundPrimePair = true;
            }
        }
    }
}

แผนภาพการทำงาน

ตัวอย่างการทำงาน

กรณี 1: มีคู่จำนวนเฉพาะ

อินพุต: 4 7 11 13 16 20 23 25 28 31 36 41 44 47 50 53 56 59 62 67
คู่จำนวนเฉพาะที่พบ:
- 7, 11 (ระยะห่าง = 4)
- 11, 13 (ระยะห่าง = 2)
- 23, 31 (ระยะห่าง = 8)
- 41, 47 (ระยะห่าง = 6)
...
ผลลัพธ์: 2 (ระยะห่างน้อยที่สุด)

กรณี 2: ไม่มีคู่จำนวนเฉพาะ

อินพุต: 4 6 8 9 10 12 14 15 16 18 20 21 22 24 25 26 27 28 30 32
ผลลัพธ์: "No prime pair was found."
ปรับปรุงล่าสุด