素数中的素数.doc

质数中的质数 给定整数N（2N8），生成所有其前任意位都是质数的N位质数。7331即是一个这样的4位质数，因为7、73和733也均为质数。在标准输出上按升序输出所有符合要求的质数。例如，对于2，输出下列9个数： 23 29 31 37 53 59 71 73 79 问题分析：首先此问题归结到底还是求素数的问题。求素数的问题是最基本的程序之一。而此问题需要解决的是如何求一个数的前面的那些位数是否是素数的问题。 我们可以按整除运算，再利用循环解决此问题。 输入所需要进行运算的位数num 调用函数fun()，此函数命名按标识符命名规则命名 fun()函数将解决此问题。 fun()函数的思想是利用循环，从2*10^num+1开始，到10^(num+1)结束。 取这个循环中这个数的首位，进行判断，是否为4、6、8，如果是则加上10^num，再进行后面的循环。因为，4、6、8不是素数，所以排除以这些数为首位的数。循环变量每次加2，因为素数除2外都是奇数。 调用yprime(i,num)，判断数i是否为所求的数。 判断原数是否为素数，再依次去掉后面的数，看是否为素数。 最后如果全部满足，则返回1，否则返回0； 判断素数，调用函数prime(n)。 程序如下： #include stdio.h #include stdlib.h #include math.h void fun(int num); int yprime(int n,int num); int prime(int n);//n是否是素数 int main() { int num=0; printf(请输入位数：); scanf(%d,num); fun(num); return 0; } //从后面往前面数，每位是否是素数 //如7331，733，73，7都是素数 //输出位数num以内的所有满足这一条件的数 void fun(int num) { int i,t,n=1; for(i=1; inum; i++) n*=10; for (i=2*n+1; in*10; i+=2)//首位为1的数也不满足条件 { t=i/n; if(t==4 ||t==6 || t==8)//首位为4、6、8的数不满足条件 i+=n; if(yprime(i,num))//输出满足条件的数 printf(%d\t,i); } } //满足条件，则返回1，不满足条件，返回0 int yprime(int n,int num) { int i; for(i=0; inum; i++) { if(!prime(n)) return 0; n/=10; } return 1; } int prime(int n)//n是否是素数 { int a=sqrt(n),i; for(i=2; i=a; i++) if(n%i==0) return 0; return 1; } 在Microsoft Windows XP SP3（1.20GHz，988MB）上运行Code::Blocks 10.05，得运行结果如下： 请输入位数：2 23 29 31 37 53 59 71 73 79 Process returned 0 (0x0) execution time : 0.266 s Press any key to continue. 请输入位数：3 233 239 293 311 313 317 373 379 593 599 719 733 739 797 Process returned 0 (0x0) execution time : 0.219 s Press any key to continue. 请输入位数：4 2333 2339 2393 2399 2939 3119 3137 3733 3739 3793 3797 5939 7193 7331 7333 7393 Process re