โปรแกรม Java แสดงจำนวนเฉพาะ (Prime Numbers) จาก 1 ถึง N

ในบทความนี้ เราจะเรียนรู้วิธีแสดงจำนวนเฉพาะจาก 1 ถึง N ในภาษา Java จำนวนเฉพาะคือจำนวนที่มีตัวหารได้แค่ 1 และตัวมันเองเท่านั้น

ข้อเท็จจริงเกี่ยวกับจำนวนเฉพาะ

• 2 เป็นจำนวนเฉพาะคู่เพียงตัวเดียว
• จำนวนเฉพาะอื่นๆ ล้วนเป็นเลขคี่
• ตัวอย่าง: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29...

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

อินพุต:

Enter the value of n: 10

เอาต์พุต:

2 3 5 7

อัลกอริทึม

1. เริ่มต้นโปรแกรม
2. ประกาศตัวแปร: n, i, counter, j
3. รับค่า N จากผู้ใช้ หรือกำหนดค่าไว้ล่วงหน้า
4. วนลูป j จาก 2 ถึง N ตรวจสอบแต่ละจำนวน
5. นับตัวหารของ j (counter) หาก counter == 2 แสดงว่าเป็นจำนวนเฉพาะ
6. แสดงผลลัพธ์
7. จบโปรแกรม

ตัวอย่างที่ 1: รับค่าจากผู้ใช้

import java.util.Scanner;

public class PrimeNumbers {
    public static void main(String arg[]) {
        int i, n, counter, j;

        Scanner scanner = new Scanner(System.in);
        System.out.println("Required packages have been imported");
        System.out.println("A reader object has been defined");
        System.out.print("Enter the n value: ");
        n = scanner.nextInt();

        System.out.print("Prime numbers between 1 to " + n + " are ");
        for (j = 2; j <= n; j++) {
            counter = 0;
            for (i = 1; i <= j; i++) {
                if (j % i == 0) {
                    counter++;
                }
            }
            if (counter == 2) {
                System.out.print(j + " ");
            }
        }
    }
}

ตัวอย่างที่ 2: กำหนดค่าไว้ล่วงหน้า

public class PrimeNumbers {
    public static void main(String arg[]) {
        int i, n = 10, counter, j;

        System.out.printf("Enter the n value is %d ", n);
        System.out.printf("\nPrime numbers between 1 to %d are ", n);

        for (j = 2; j <= n; j++) {
            counter = 0;
            for (i = 1; i <= j; i++) {
                if (j % i == 0) {
                    counter++;
                }
            }
            if (counter == 2) {
                System.out.print(j + " ");
            }
        }
    }
}

การเพิ่มประสิทธิภาพ (Optimization)

ลูปในตัวอย่างตรวจสอบถึง j ซึ่งช้า (O(n²)) สามารถปรับปรุงได้:

// ตรวจสอบแค่ถึง sqrt(j) เพียงพอ
for (i = 2; i * i <= j; i++) {
    if (j % i == 0) {
        counter++;
        break;
    }
}
// หรือใช้ Sieve of Eratosthenes สำหรับ N ใหญ่ (O(n log log n))