查找指定范围的自然数的所有质数，实现起来并不难，但是哪种算法效率最高，速度最快才是重点，我列出几种算法：
1、将待判断的值与小于它而且不小于2的所有数求余数
public static List<Integer> getprimeV1(int max){
List<Integer> list = new ArrayList<>();
boolean flag;
int times = 0;
for(int i=2;i<=max;i++){
flag=false;
if(!flag) {
for (int j = 2; j < i; j++) {
times++;
if (i % j == 0) {
flag = true;
break;
}
}
}
if(!flag){
list.add(i);
}
}
System.out.println(“循环次数：”+times);
return list;
}
2、将待判断的值与比它小的所有素数求余数
public static List<Integer> getprimeV2(int max){
List<Integer> list = new ArrayList<>();
boolean flag;
int times = 0;
for(int i=2;i<=max;i++){
flag=false;
if(i>2){
for (Integer num : list) {
times++;
if(i%num==0) {
flag = true;
break;
}
}
}
if(!flag){
list.add(i);
}
}
System.out.println(“循环次数：”+times);
return list;
}
3、将待判断的值与不大于它的平方根而且不小于2的所有数求余数
public static List<Integer> getprimeV3(int max){
List<Integer> list = new ArrayList<>();
boolean flag;
int times = 0;
for(int i=2;i<=max;i++){
flag=false;
if(!flag) {
for (int j = 2; j <= Math.sqrt(i); j++) {
times++;
if (i % j == 0) {
flag = true;
break;
}
}
}
if(!flag){
list.add(i);
}
}
System.out.println(“循环次数：”+times);
return list;
}
4、将待判断的值与不大于它的平方根的所有素数求余数
public static List<Integer> getprimeV4(int max){
List<Integer> list = new ArrayList<>();
boolean flag;
int times = 0;
for(int i=2;i<=max;i++){
flag=false;
if(i>2){
for (int j=0;list.get(j)<=Math.sqrt(i);j++) {
times++;
if(i%list.get(j)==0) {
flag = true;
break;
}
}
}
if(!flag){
list.add(i);
}
}
System.out.println(“循环次数：”+times);
return list;
}
针对以上四种算法：
1）当我传入参数为100的时候，得到的循环次数从上往下分别为：
1133、411、236 、181，他们消耗的时间很短，没有可比性，所以可以换一个大一点的参数测试；
2）当我传入参数为1000000时，他们消耗的时间从上往下大概分别为：
150s，80s，0.8s，0.3s
从测试结果看，不同的算法，计算效率就是差别很大，学好算法，对于提高工作效率有很大的帮助。如有更好的算法，欢迎指正和补充，谢谢。