企业网站制作正规公司_知名企业有哪些_百度推广的价格表_百度竞价关键词出价技巧

很多题涉及质数，比较好的方法是直接生成一个质数数组，要用的时候直接访问就行了，一个比最原始生成质数数组快的比较常用的生成质数算法–埃式筛

考虑这样一件事情：对于任意一个大于 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));}
}