埃筛法（算法，java）（查找100以内的素数）

目录

原理：

GIF展示： 

 代码展示：

提供一种判断一个数是否为素数的代码（本人代码中为使用）（Python）

java代码： 

运行结果:

本人了解尚浅，辩证参考。 

原理：

       用已经筛选出来的素数去过滤所有能够被它整除的数。. 这些素数就像是筛子一样去过滤自然数，最后被筛剩下的数自然就是不能被前面素数整除的数，根据素数的定义，这些剩下的数也是素数。

GIF展示： 

 代码展示：

提供一种判断一个数是否为素数的代码（本人代码中为使用）（Python）

         寻找素数最朴素的方法当然是一个一个遍历，我们依次遍历每一个数，然后分别判断是否是素数。所以问题的核心又回到了判断素数上，那么怎么判断一个数是不是素数呢？素数的性质只有一个，就是只有1和它本身这两个因数，我们要判断素数也只能利用这个性质。所以可以想到，假如我们要判断n是否是素数，可以从2开始遍历到n-1，如果这n-1个数都不能整除n，那么说明n就是素数。

def is_prime(n):if n % 2 == 0 and n != 2:return Falsefor i in range(3, int(math.sqrt(n) + 1)):if n % i == 0:return Falsereturn n != 1

java代码： 

package SF;import java.util.LinkedList;public class Intasf {//暴力寻找public static LinkedList asf1(int num){LinkedList list=new LinkedList();for (int i = 2; i <=num; i++) {if (i==2){list.add(i);continue;}if (i%2==0)continue;int j;for ( j = 1; j < list.size(); j++) {if (i%list.get(j)==0)break;}if (j==list.size()){list.add(i);}}return list;}//埃筛法public static int[] asf2(int num){int[] list=new int[num];for (int i = 0; i < list.length; i++) {list[i]=0;}//标记出所有的合数for (int i = 2; i <=num ; i++) {if (list[i-1] == 0) {for (int j = i*i; j <=num; j+=i) {list[j-1]=j;}}}//取出质数int count=0;list[0]=0;//1不是素数for (int i = 1; i < num; i++) {if (list[i]==0){list[i]=i+1;count++;}else {list[i]=0;}}int[] newlist=new int[count];int t=0;for (int i = 0; i < num; i++) {if (list[i]!=0){newlist[t]= list[i];t++;}}return newlist;}public static void main(String[] args) {LinkedList list1=asf1(100);for (int i = 0; i < list1.size(); i++) {System.out.print(list1.get(i)+" ");}System.out.println();System.out.println(list1.size());int[] list2=asf2(100);for (int i = 0; i < list2.length; i++) {System.out.print(list2[i]+" ");}System.out.println();System.out.print(list2.length);}
}

运行结果:

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 
25
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 
25
进程已结束,退出代码0

本人了解尚浅，辩证参考。 

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！