แสดงจำนวนเฉพาะโดยใช้หลักตะแกรงของเอราทอสเทนีส

โจทย์

In mathematics, the sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to any given limit.

• Create a list of consecutive integers from 2 through n: (2, 3, 4, …, n).
• Initially, let p equal 2, the smallest prime number.
• Enumerate the multiples of p by counting in increments of p from 2p to n, and mark them in the list (these will be 2p, 3p, 4p, …; the p itself should not be marked).
• Find the smallest number in the list greater than p that is not marked. If there was no such number, stop. Otherwise, let p now equal this new number (which is the next prime), and repeat from step 3.
• When the algorithm terminates, the numbers remaining not marked in the list are all the primes below n.

โค้ด

import java.util.Scanner;
 
public class Program {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
 
        int n = scanner.nextInt();
 
        int[] candidate = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            candidate[i] = i;
        }
 
        int currentNumber = 2;
        while (currentNumber * currentNumber <= n) {
            if (candidate[currentNumber] != Integer.MIN_VALUE) {
                int product = currentNumber * 2;
                while (product <= n) {
                    candidate[product] = Integer.MIN_VALUE;
                    product += currentNumber;
                }
            }
            currentNumber++;
        }
 
        for (int number : candidate) {
            if (number >= 2) {
                System.out.printf("%d ", number);
            }
        }
 
    }
}

คำอธิบาย

1. การรับข้อมูลและเตรียมอาร์เรย์

Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
 
int[] candidate = new int[n + 1];
for (int i = 2; i <= n; i++) {
    candidate[i] = i;
}

• รับค่า n จากผู้ใช้
• สร้างอาร์เรย์ candidate ขนาด n+1 (เพื่อให้ดัชนีตรงกับตัวเลข)
• เติมค่าตั้งแต่ 2 ถึง n ลงในอาร์เรย์

2. การคัดกรองจำนวนที่ไม่ใช่จำนวนเฉพาะ

int currentNumber = 2;
while (currentNumber * currentNumber <= n) {
    if (candidate[currentNumber] != Integer.MIN_VALUE) {
        int product = currentNumber * 2;
        while (product <= n) {
            candidate[product] = Integer.MIN_VALUE;
            product += currentNumber;
        }
    }
    currentNumber++;
}

• เริ่มจากจำนวนแรก (2)
• หาผลคูณของจำนวนนั้นกับตัวคูณต่างๆ
• ทำเครื่องหมาย (mark) จำนวนที่เป็นผลคูณด้วยค่า Integer.MIN_VALUE
• ทำซ้ำจนครบทุกจำนวน

3. การแสดงผลจำนวนเฉพาะ

for (int number : candidate) {
    if (number >= 2) {
        System.out.printf("%d ", number);
    }
}

• วนลูปผ่านอาร์เรย์
• แสดงเฉพาะจำนวนที่มากกว่าหรือเท่ากับ 2 และไม่ได้ถูกทำเครื่องหมาย

หลักการทำงาน

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

กรณี n = 10

1. สร้างอาร์เรย์: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
2. เริ่มจาก 2:
   • ทำเครื่องหมายที่ 4, 6, 8, 10 (คูณ 2)
3. ต่อไปที่ 3:
   • ทำเครื่องหมายที่ 6, 9 (คูณ 3)
4. ต่อไปที่ 5:
   • ทำเครื่องหมายที่ 10 (คูณ 5)
5. ผลลัพธ์: 2, 3, 5, 7 (จำนวนเฉพาะที่เหลือ)