词条 | 筛选法 |
释义 | 筛选法又称筛法,是求不超过自然数N(N>1)的所有质数的一种方法。据说是古希腊的埃拉托斯特尼(Eratosthenes,约公元前274~194年)发明的,又称埃拉托斯特尼筛子。 具体做法是:先把N个自然数按次序排列起来。1不是质数,也不是合数,要划去。第二个数2是质数留下来,而把2后面所有能被2整除的数都划去。2后面第一个没划去的数是3,把3留下,再把3后面所有能被3整除的数都划去。3后面第一个没划去的数是5,把5留下,再把5后面所有能被5整除的数都划去。这样一直做下去,就会把不超过N的全部合数都筛掉,留下的就是不超过N的全部质数。因为希腊人是把数写在涂腊的板上,每要划去一个数,就在上面记以小点,寻求质数的工作完毕后,这许多小点就像一个筛子,所以就把埃拉托斯特尼的方法叫做“埃拉托斯特尼筛”,简称“筛法”。(另一种解释是当时的数写在纸草上,每要划去一个数,就把这个数挖去,寻求质数的工作完毕后,这许多小洞就像一个筛子。) C语言实现筛选法先解释一下筛选法的步骤: <1> 先将1挖掉(因为1不是素数)。 <2> 用2去除它后面的各个数,把能被2整除的数挖掉,即把2的倍数挖掉。 <3> 用3去除它后面的各数,把3的倍数挖掉。 <4> 分别用5…各数作为除数去除这些数以后的各数。 上述操作需要一个很大的容器去装载所有数的集合,只要满足上述条件,即2的N次方的全部置0,3的N次方的全部置0,4的N次方的全部置0.。。。一直到这个数据集合的末尾,这样一来不为0的数就是素数了,然后按下标在里面进行查找就好了 筛选法程序如下 #include<stdio.h> int 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<50000;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("素数\"); else printf("合数\"); scanf("%d",&n); } return 0; } 筛选法求某项自然数A之内的素数(C语言)实现一1.抽象步骤 <1>先将1去掉 <2>将2的倍数去掉。 <3>将3的倍数去掉。 …… <i>将i的倍数去掉。 …… 一直到A。 2.具体化 以数组array[n]为例,其中array[n]=n+1; 循环开始 <1> 判断array[0]的值。 array[0]的值是1;不执行操作 <2> 判断array[1]的值。 array[1]的值是2; 用array[1]去除它后面的array[2]、array[3]、array[4]……array[n]; 能被array[1]整除的,例如array[3](值为4)、array[5](值为6),全部置1; 即:if (array[i]%array[1]==0) array[i]=1; i=2,3,4……n <3> 判断判断array[2]的值。 array[2]的值是3; 用array[2]去除它后面的各数,把array[2]的倍数全部置1。 比如array[8](值为9),array[14](值为15),全部置为"1"。 即:if (array[i]%array[2]==0) array[i]=1; i=3,4,5……n <4> 判断array[3]的值。 array[3]原本的值为4,但是经过步骤<2>,现在array[3]的值为1; 换句话说,如果array[3]的值为1,那么它一定可以被 array[2] 和 array[3] 中的某一个整除。 所以array[3]曾经是合数,不执行操作。 ……………………… <i> 判断array[i]的值。 如果 array[i]==1,那么array[i]一定可以被array[2]、array[3]、……array[i-1]中的某一个数整除 所以曾经的array[i]是合数,不执行任何操作。 否则 array[i]!=1,那么array[i]是素数。 用array[i]去除array[i+1]、array[i+2]、……array[n]。 能被array[i]整除的各项,全部置1。 ……………………… <n> 判断array[n]的值。 如果 array[n]==0,那么array[n]一定可以被array[2]~array[n-1]中的一项整除。 所以array[n]是合数,不执行任何操作。 如果 array[n]!=0,那么array[2]~array[n-1]都不能将它整除。 所以 array[n]是素数。 循环结束。 经过以上循环,所有合数都被置“1”,输出所有非“1”的array[]。 即if(array[i]!=1) printf("%d",array[i]); 程序结束。 3.代码实现 #define A 100 //随意取个自然数范围 #include <stdio.h> void main() { int i,j; int array[A]; //初始化数组 clrscr(); //清理屏幕 for (i=0;i<A;i++) array[i]=i+1; //初始化数组 for (i=0;i<A;i++) { //循环开始,操作步骤<i> if( array[i]!=1 ) //如果array[i]的值不为"1" { for(j=i+1;j<A;j++) //执行操作:用array[i]除后面的array[i+1]~array[n] { if( array[j]%array[i]==0) //能被array[i]整除的即为合数。 array[j]=1; //合数都被重置为"1"。 } } } //循环结束 j=0; //建立一个换行标记j for(i=0;i<A;i++) //循环开始 { if(array[i]!=1) //如果array[i]为素数(即值不为"1") { printf("%4d",array[i]); //输出array[i] j++; //标记自加 if (j%5==0) putchar('\'); //每输出5个素数另起一行接着输出 } } getch(); //按任意键继续 } 实现二“筛选法”原理:先把N个自然数按次序排列起来。1不是质数,也不是合数,要划去。第二个数2是质数留下来, 而把2后面所有能被2整除的数都划去。2后面第一个没划去的数是3,把3留下,再把3后面所有 能被3整除的数都划去。3后面第一个没划去的数是5,把5留下,再把5后面所有能被5整除的数 都划去...直至留下的数全为素数 ----------------------纯粹按“筛选法”原理实现-------------------------- #include<stdio.h> void main(){ int i; int N,count,p=0; int r[1001];//限制数据量大小为1000 printf("你想求多少以内的素数:"); scanf("%d",&N); for(i=1;i<=N;i++)//为方便计,从1起 r[i]=1; count=2;//筛选起点为2 while(count<=N/2){//显然:count不会超过N/2,必能使留下的数全为素数。 for(i=count+1;i<=N;i++){ if(r[i]==1&&i%count==0){ r[i]=0; } } for(i=count+1;i<=N;i++){ if(r[i]==1){ count=i; break; } } } printf("%d以内的素数为:\",N); for(i=2;i<=N;i++) if(r[i]==1){ p++; if(p%10==0)//增设p为输出换行 printf("\"); printf("%d ",i); } printf("\"); } ----------------------纯粹按“筛选法”原理实现-------------------------- |
随便看 |
百科全书收录4421916条中文百科知识,基本涵盖了大多数领域的百科知识,是一部内容开放、自由的电子版百科全书。