筛选法求素数

解题思路

• 埃托拉斯筛选法
• 快速求0的数量

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = 0;
        int[] primes = new int[105];
        int[] st = new int[105];
        Arrays.fill(st, 0);
        for(int i = 2; i <= n; i++){
            if(st[i] == 0){
                primes[k++] = i;
                for(int j = i+i; j <= n; j+=i){
                    st[j] = 1;
                }
            }
        }
        for(int i = 0; i < k; i++){
            System.out.print(primes[i]+" ");
        }
        System.out.println();
        System.out.println(n-k-1);
    }

}