筛选法，筛选法找素数程序

1，筛选法找素数程序

var a:array [1..10000] of boolean; i,j:integer; begin for i:=1 to 10000 do a[i]:=true; for i:=2 to 5000 do begin if a[i] then for j:=2 to trunc(10000/i) do a[i*j]:=false end; j:=0; for i:=2 to 10000 do if a[i] then begin write(i:5); j:=j+1; if j mod 5=0 then writeln; end; end.

筛选法找素数程序

2，筛选法数学

筛选法又称筛法，是求不超过自然数N（N＞1）的所有质数的一种方法。据说是古希腊的埃拉托斯特尼（Eratosthenes，约公元前274～194年）发明的，又称埃拉托斯特尼筛子。具体做法是：先把N个自然数按次序排列起来。1不是质数，也不是合数，要划去。第二个数2是质数留下来，而把2后面所有能被2整除的数都划去。2后面第一个没划去的数是3，把3留下，再把3后面所有能被3整除的数都划去。3后面第一个没划去的数是5，把5留下，再把5后面所有能被5整除的数都划去。这样一直做下去，就会把不超过N的全部合数都筛掉，留下的就是不超过N的全部质数。因为希腊人是把数写在涂腊的板上，每要划去一个数，就在上面记以小点，寻求质数的工作完毕后，这许多小点就像一个筛子，所以就把埃拉托斯特尼的方法叫做“埃拉托斯特尼筛”，简称“筛法”。（另一种解释是当时的数写在纸草上，每要划去一个数，就把这个数挖去，寻求质数的工作完毕后，这许多小洞就像一个筛子。）

筛选法数学

3，C语言中筛选法是怎么考虑的就是分几个步骤考虑筛选出素数

1、先解释一下筛选法的步骤：<1> 先将1挖掉(因为1不是素数)。<2> 用2去除它后面的各个数，把能被2整除的数挖掉，即把2的倍数挖掉。<3> 用3去除它后面的各数，把3的倍数挖掉。<4> 分别用5…各数作为除数去除这些数以后的各数。上述操作需要一个很大的容器去装载所有数的集合，只要满足上述条件，即2的N次方的全部置0，3的N次方的全部置0，4的N次方的全部置0.。。。一直到这个数据集合的末尾，这样一来不为0的数就是素数了，然后按下标在里面进行查找就好了2、例程:#include "stdafx.h"#include using namespace std; #define N 1001 void main(void){ int a[N],i,j,k; for(i=1;i for(i=2;i if(a[i]) for(j=i+i;j for(k=0,i=2;i if(a[i]) printf(++k%15 ? "%-4d" : "%-4d\n",i); printf("\n"); }

先解释一下筛选法的步骤：<1> 先将1挖掉(因为1不是素数)。<2> 用2去除它后面的各个数，把能被2整除的数挖掉，即把2的倍数挖掉。<3> 用3去除它后面的各数，把3的倍数挖掉。<4> 分别用4、5…各数作为除数去除这些数以后的各数。上述操作需要一个很大的容器去装载所有数的集合，只要满足上述条件，即2的N次方的全部置0，3的N次方的全部置0，4的N次方的全部置0.。。。一直到这个数据集合的末尾，这样一来不为0的数就是素数了，然后按下标在里面进行查找就好了筛选法程序如下 #includeint main() { int x[100001]; int temp,n, i; //初始化数组 for(i=0;i<100001;i++) x[i]=0; //初始化数组完成 /* 预计结果，数组中质数为0，其它为1 */ x[0]=x[1]=1;//因为 0和1不能通过计算得到，所以只能手工置1 ，1即不是合数也不是质数for(i=2;i<100001;i++) {//循环数组中的每个数 if(x[i]==0){//如果该数所存的值为0，即第一次接触此数 temp=2*i;//将它的二倍，及n倍（要小于100000），都置为1，因为这些数都能被i整除 while(temp<=100000) { x[temp]=1; temp+=i; } } } scanf("%d",&n); while(n != 0) { if(x[n]==0) printf("素数\n"); else printf("合数\n"); scanf("%d",&n); } return 0; }如果你觉得这个方法不好理解，你可以用上面他们写的那些常规算法，但是数字过大的话，算起来是很慢的

先把2的倍数标记，再把3的倍数标记。以后就依次把数组中未标记的数的倍数都标记，直到整个数组遍历，则完结。数组中未标记的就是素数。这里的倍数是从2开始的整数倍！#include "stdafx.h"#include using namespace std; #define N 1001 void main(void){ int a[N],i,j,k; for(i=1;i for(i=2;i if(a[i]) for(j=i+i;j for(k=0,i=2;i if(a[i]) printf(++k%15 ? "%-4d" : "%-4d\n",i); printf("\n"); }

main()int i,j,h,k=0,p[100]=for(i=1;i<200;i++)a[i]=i+1;/*将所有候选数放入筛中*/for(i=0;i<200;i++)for(j=0;j<200;j++)if(a[i]!=0)p[k]=a[i];/*将最小数放入素数集合p中*/for(h=k;h<200;h++)if(a[h]%p[k]==0)a[h]=0;/*将这个素数的倍数从筛中删去*/k++;}i=0;printf("primes:");while(p[i]!=0)}

先解释一下筛选法的步骤：<1> 先将1挖掉(因为1不是素数)。<2> 用2去除它后面的各个数，把能被2整除的数挖掉，即把2的倍数挖掉。<3> 用3去除它后面的各数，把3的倍数挖掉。<4> 分别用5…各数作为除数去除这些数以后的各数。上述操作需要一个很大的容器去装载所有数的集合，只要满足上述条件，即2的N次方的全部置0，3的N次方的全部置0，4的N次方的全部置0.。。。一直到这个数据集合的末尾，这样一来不为0的数就是素数了，然后按下标在里面进行查找就好了

C语言中筛选法是怎么考虑的就是分几个步骤考虑筛选出素数