素数是只能被一或者自身整除的整数，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一定不是
素数。
上面代码演示为埃拉托斯特尼筛法