868. 筛质数 Java题解 （埃氏筛，线性筛）

质数 Java题解 （埃氏筛，线性筛）"/>

868. 筛质数 Java题解 （埃氏筛，线性筛）

输入样例：

8

输出样例：

4

解题思路：

埃氏筛质数:又叫朴素筛法，求某个区间的质数个数时，从2开始，将每个数的倍数都筛掉，剩下的数就是质数。缺点：会对某个数重复筛。时间复杂度为O(nlogn)

线性筛法：对埃氏筛的优化，埃氏筛的任意一个数都被它的因数筛了一遍，实际上只需要筛一次就行，即每次只用最小质因子筛，不会被重复筛，时间复杂度为O(nloglogn)，非常接近线性。

两种筛法的相同点：都可以在筛选时找到质数的个数，求出区间内的所有质数，并且能求出每个数的最小质因子。

不同点：在10^6内，效率都差不多，但10^7时，线性筛明显比埃氏筛快一倍。

Java代码：（埃氏筛）

import java.io.*;public class Main {public static void main(String[] args) throws NumberFormatException, IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));int n = Integer.parseInt(br.readLine());getPrime(n);}public static void getPrime(int n) {boolean []st = new boolean[n + 1];  // 状态数组，标识是否被筛掉int []primes = new int[n + 1];  // 存放质数int cnt = 0;  //质数的个数for(int i = 2; i <= n; i++) { // 埃氏筛if(!st[i]) primes[cnt++] = i;for(int j = i + i; j <= n; j += i) // 将每个数的倍数都过滤掉，标志为truest[j] = true;}System.out.println(cnt);}
}

Java代码： （线性筛）

import java.io.*public class Main {public static void main(String[] args) throws NumberFormatException, IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));int n = Integer.parseInt(br.readLine());getPrime(n);}public static void getPrime(int n) {boolean []st = new boolean[n + 1];  // 状态数组，标识是否被筛掉int []primes = new int[n + 1];  // 存放质数int cnt = 0;  //质数的个数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;}}System.out.println(cnt);}
}