蓝桥杯练习笔记(十九-质数筛)
很多题涉及质数,比较好的方法是直接生成一个质数数组,要用的时候直接访问就行了,一个比最原始生成质数数组快的比较常用的生成质数算法–埃式筛
考虑这样一件事情:对于任意一个大于 1 的正整数 n,那么它的 x 倍就是合数(x > 1)。利用这个结论,我们可以避免很多次不必要的检测。
如果我们从小到大考虑每个数,然后同时把当前这个数的所有(比自己大的)倍数记为合数,那么运行结束的时候没有被标记的数就是素数了。
参考文章:OI Wiki
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
public static void main(String[] args) {
int n=100005;
ArrayList<Integer> isprime=new ArrayList<>(100005);
Collections.fill(isprime,1);
ArrayList<Integer> prime=new ArrayList<>();
// 通过添加n个元素来确保ArrayList有足够的容量
for (int i = 0; i <= n; i++) {
isprime.add(1);
}
isprime.set(0,0);
isprime.set(1,0);
for(int i=2;i*i<=n;i++)
{
if(isprime.get(i)>0)
{
prime.add(i);
for(int j=i*i;j<=n;j+=i)
{
isprime.set(j,0);
}
}
}
//打印结果
for(int i=0;i<prime.size();i++)System.out.println(prime.get(i));
}
}