蓝桥杯刷题记录之质数

记录

题目编号 1557

import java.util.Scanner;

public class Main{
    static Scanner s = new Scanner(System.in);

    static long n;
    static int cnt=0;
    static boolean[] st = new boolean[100000];
    static int[] primes = new int[10000];
    static void primes(){
        for(int i=2;i<n;i++){
            if(!st[i])
                primes[cnt++]=i;
            for(int j=0;primes[j] <=n/i;j++){
                st[primes[j]*i]=true;
                if(i % primes[j]==0)
                    break;
            }
        }
    }
    public static void main(String[] args) {
        n = s.nextLong();
        primes();
        for(int i=2;i<n;i++)
            if(!st[i])
                System.out.print(i+" ");
        System.out.println("\n" + cnt);

        s.close();
    }
}