找出質數 - 使用篩法－Afutseng's Blog

For given value of N (say, 30), first write down all the integers from 2 to N:
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Delete all the multiples of the first number in the sequence (2):
2 3 5 7 9 11 13 15 17 19 21 23 25 27 29
Now move onto the next number (3) and do the same again:
2 3 5 7 11 13 17 19 23 25 29

Do 5 next:
2 3 5 7 11 13 17 19 23 29

The next number in the sequence (7) is greater than the square root of N, so we can stop there. The numbers that are left are our prime numbers.

To write your program, use a 1-D array of booleans - one element for each integer up to N. Set them all to true to begin with, but each time you delete an integer, set the corresponding array element to false. The array indices of the true values that are left at the end correspond to the prime numbers.

import java.util.*;
public class prime{
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int N = input.nextInt();
        boolean[] prime = new boolean[N+1];
        for(int i=2;i<=N;i++)
            prime[i] = true;
        for(int i=2;i<=Math.sqrt(N);i++){
            for(int j=2;j<=(N/i);j++){
                if(i*j<=N)
                    prime[i*j] = false;
            }
        }
        for(int i=2;i<=N;i++)
            if(prime[i])
                System.out.println(i);
    }
}