求最大素数原理（求素数质数的几种算法对比）

查找指定范围的自然数的所有质数，实现起来并不难，但是哪种算法效率最高，速度最快才是重点，我列出几种算法：

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 从测试结果看，不同的算法，计算效率就是差别很大，学好算法，对于提高工作效率有很大的帮助。如有更好的算法，欢迎指正和补充，谢谢。