请统计出n以内所有的素数个数 埃拉托斯特尼筛法

素数是只能被一或者自身整除的整数，1不是素数。

要统计n以内的所有素数，最常用的方法就是校验每一个数字是都是不是素数，但是当n的值很大的时候，这个方法的耗时将会很长。

不如我们换个思路，我们能不能直接生成n以内的素数，然后直接输出长度呢？

import java.util.Scanner;

public class Main {

? ? public static int countPrimes(int n) {
? ? ? ? if (n <= 2) {
? ? ? ? ? ? return 0;
? ? ? ? }

? ? ? ? boolean[] isPrime = new boolean[n + 1];
? ? ? ? for (int i = 2; i <= n; i++) {
? ? ? ? ? ? isPrime[i] = true;
? ? ? ? }

? ? ? ? for (int p = 2; p * p <= n; p++) {
? ? ? ? ? ? if (isPrime[p]) {
? ? ? ? ? ? ? ? for (int i = p * p; i <= n; i += p) {
? ? ? ? ? ? ? ? ? ? isPrime[i] = false;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }

? ? ? ? int count = 0;
? ? ? ? for (int i = 2; i <= n; i++) {
? ? ? ? ? ? if (isPrime[i]) {
? ? ? ? ? ? ? ? count++;
? ? ? ? ? ? }
? ? ? ? }

? ? ? ? return count;
? ? }

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

? ? ? ? int result = countPrimes(n);
? ? ? ? System.out.println(result);
? ? }
}

以上的代码是使用筛选法来生成素数列表，最后通过统计列表素数个数得出结果。在统计素数个数的题目中，生成比判断更加快速。

1.埃拉托斯特尼筛法

埃拉托斯特尼筛法是一种简单而有效的生成素数的算法。它的基本

思想是从2、开始，将每个素数的倍数标记为合数，真到筛子中的所

有数字都被处理完为止。具体步骤如下：

（1）创建一个长度为n的布尔数组，初始值都为true。

（2）从2开始，将每个素数的倍数标记为false。

（3）当处理完所有小于等于n的数时，所有值为true的下标对应

的数字就是素数。

该算法的时间复杂度为0(nloglogn)，空间复杂度为0(n)。

2.米勒-拉宾素性检验

米勒-拉宾素性检验是一种基于费马小定理的概率算法，用于判断

一个数是否为素数。它的基本思想是：对于一个大于 2的整数n,

如果存在一个整数a，使得a^(n-1)mod n不等于1，则n一定不是

素数。

上面代码演示为埃拉托斯特尼筛法