【埃氏筛法】筛选N内素数（非暴力）

解题思路:

素数的特点：素数乘以任何一个数都能得到一个合数

根据这个特点筛掉N中的合数，剩下的就是素数咯
在座的各位有志青年请看注释！
注意事项:

埃筛法是比较早期的一个纯暴力的改进算法

其实还有一个线性筛，它的效率更高

埃筛用在范围小的数还是很欧克的，

要想判断更大范围的素数还是用线性筛合适！

感兴趣的可以去学习学习！

参考代码:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Scanner;
import java.util.Stack;

/**
 * @Author:杨雨彤
 * @date:2024/1/9 20:42
 */
public class daydayone {
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int n =Integer.parseInt(br.readLine());
        boolean[]isprime=new boolean[n+1];//状态数组 默认false全为素数
        int[]prime=new int[n+1];//用来存判断出来的素数，因为事先不知道N内有多少素数，所以初始容量为N
        int count=0;//用来记录素数的个数，方便后续的遍历
        for (int i = 2; i <=n; i++) {//遍历N内的数字
            if(!isprime[i]){//如果是素数，这里采用下标和数字对应的关系方便理解，isprime[2]就是数字2的状态
                prime[count++]=i;//将数字i添加到素数数组中
                for (int j = 2; i*j<=n ; j++) {//拿到一个素数后，开始筛出n内和合数。
                    isprime[i*j]=true;//素数×任何数(不能×1哦）都是合数，将i*j这个数的isprime[i*j]置为true
                }
            }
        }
        for (int i = 0; i <count ; i++) {//遍历素数数组
            System.out.print(prime[i]);
            System.out.println();
        }


    }
}