题目描述

筛质数

JAVA 代码

埃式筛法

import java.util.*;
import java.io.*;

class Main{

    static int N = 1000010;
    static int[] primes = new int[N];
    static boolean[] st = new boolean[N];
    static int cnt;

    static void getPrimes(int x){
        //埃式筛法

        //前面质数都会被存起来.  
        // 2 - 3， 4被晒 5存入. 
        for(int i=2; i<=x; i++){
            if(st[i]) continue;
            //把质数存起来. 
            primes[cnt++] = i;

            //每次增长一倍
            //只用晒掉质数的倍数
            for(int j=i+i; j<=x; j+=i){
                st[j] = true;
            }
        }
    }

    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        getPrimes(n);
        System.out.println(cnt);
    }

}

线性晒法

import java.util.*;
import java.io.*;

class Main{

    static int N = 1000010;
    static int[] primes = new int[N];
    static boolean[] st = new boolean[N];
    static int cnt;

    static void getPrimes(int x){
        //线性筛法


        for(int i=2; i<=x; i++){
            if(!st[i]){
                //把质数存起来. 
                primes[cnt++] = i;
            }
            //质数小于 sqrt[x]
            for(int j=0; primes[j]<=x/i; j++){

                st[primes[j]*i] = true;
                // n 只会被最小质因子晒掉. 
                if(i%primes[j] == 0) break;
            }
        }
    }

    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        getPrimes(n);
        System.out.println(cnt);
    }

}