蓝桥杯——趣味素数问题（2017.2.3）

一、基本素数问题回顾

1. 求给定范围start~end之间的所有素数（1<=start<end）

源代码：

#include <stdio.h>#include <math.h>int main(){	int start,end;	int i,j,k,num,flag;	while(scanf("%d %d",&start,&end)!=EOF)	{		num=0;		for(i=start;i<=end;i++)		{			k=sqrt(i);			flag=1;			for(j=2;j<=k;j++)			{				if(i%j==0)				{					flag=0;					break;				}			}			if(flag==1)           //此处写 j>=k+1 亦可			{				num++;				PRintf("%d ",i);				if(num%10==0)					printf("/n");			}		}		printf("/n%d~%d之间的素数个数为%d/n",start,end,num);	} 	return 0;}程序截图：
2. 输入一个正整数n，判断该数是否为素数
源代码：
#include <stdio.h>#include <math.h>int is_Prime(int n){	int i;	int flag=1;	for(i=2;i<=sqrt(n);i++)	{		if(n%i==0)		{			flag=0;			break;		}	}	return flag;}int main(){	int n;	while(scanf("%d",&n)!=EOF)	{		if(is_Prime(n))			printf("%d是素数/n",n);		else			printf("%d不是素数/n",n);	}	return 0;}
程序截图：
3. 输入一个正整数n，输出第n个素数（n<=10000）
源代码：
#include <stdio.h>#include <math.h>#define maxn 100000void Prime(int prime[],int n){	int i,j,k;	int flag,t=0;	int low,high,mid; 	for(i=2;i<=150000;i++)	{		k=sqrt(i);		flag=1;		for(j=2;j<=k;j++)		{			if(i%j==0)			{				flag=0;				break;			}		}		if(flag==1)			prime[t++]=i;	}	low=0,high=t-1;                  //因素数数组较大，用折半查找法素数数组下标，若下标+1=n，则输出对应第n个素数 	while(low<=high)	{		mid=(low+high)/2;		if(mid==n)		{			printf("第%d个素数是：%d/n",n,prime[n-1]);			break;		}		else if(mid<n)			low=mid+1;		else			high=mid-1;	}	printf("/n");}int main(){	int n,prime[maxn]={0};	while(scanf("%d",&n)!=EOF)		Prime(prime,n); 	return 0;}
程序截图：
二、哥德巴赫猜想
         输入2000以内不小于4的正偶数n，将其分解为两个素数之和（即验证哥德巴赫猜想对2000以内的正偶数恒成立）
源代码：
#include <stdio.h>#include <math.h>#define maxn 2000void Split(int prime[],int n)            //正偶数分解 {	int i,j,k;	int num=0,flag;	for(i=2;i<=2000;i++)	{		k=sqrt(i);		flag=1;		for(j=2;j<=k;j++)		{			if(i%j==0)			{				flag=0;				break;			}		}		if(flag==1)			prime[num++]=i;	}	for(i=0;i<num;i++)                   //表示为两个素数之和，且前者小于后者 	{		for(j=0;j<num;j++)		{			if(n==prime[i]+prime[j] && prime[i]<=prime[j])				printf("%d=%d+%d/n",n,prime[i],prime[j]);		}	}}int main(){	int n,prime[maxn]={0};	while(scanf("%d",&n)!=EOF)		Split(prime,n);	return 0;}程序截图：
另：控制不只一组解的情况下，输出第一个素数最小的那组解
源代码：
#include <stdio.h>#include <math.h>#define maxn 2000void Split(int prime[],int n){	int i,j,k;	int num=0,flag,ok;	for(i=2;i<=2000;i++)	{		k=sqrt(i);		flag=1;		for(j=2;j<=k;j++)		{			if(i%j==0)			{				flag=0;				break;			}		}		if(flag==1)			prime[num++]=i;	}	for(i=0;i<num;i++)	{		for(j=0;j<num;j++)		{			ok=0;                                            //输出一组解的标志 			if(n==prime[i]+prime[j] && prime[i]<=prime[j])   //发现符合要求的一组解，输出之，并将ok标志置为1 			{				printf("%d=%d+%d/n",n,prime[i],prime[j]);				ok=1;			}			if(ok==1)                                        //随后不在查找其他符合要求的解，直接跳出内外层循环 				break;		}		if(ok==1)			break;	}}int main(){	int n,prime[maxn]={0};	while(scanf("%d",&n)!=EOF)		Split(prime,n);	return 0;}程序截图：
三、可逆素数
        从小到大输出所有4位数的可逆素数
        可逆素数是指：一个素数将其各位数字的顺序倒过来构成的反序数也是素数
源代码：
#include <stdio.h>#include <math.h>int is_Prime(int n){	int i;	int flag=1;	for(i=2;i<=sqrt(n);i++)	{		if(n%i==0)		{			flag=0;			break;		}	}	return flag;}int main(){	int i,j,wei;	int reversenum,num=0;	for(i=1000;i<=9999;i++)	{		if(is_Prime(i))		{			j=i,wei=1000,reversenum=0;			while(j>0)                                  //求一个数的“反序数”，如1234->4321 			{				reversenum+=((j%10)*wei);				j/=10;				wei/=10;			}			if(is_Prime(reversenum))			{				printf("%d -- %d    ",i,reversenum);				num++;				if(num%4==0)                           //控制每输出4组数换一行 					printf("/n");			} 		}	}	return 0;}
程序截图：
四、回文素数
        求出所有不超过1000的回文素数
        回文素数是指：一个整数n，其为素数，且从左向右和从右向左读数值都相同
源代码：
#include <stdio.h>#include <math.h>int is_Prime(int n){	int i;	int flag=1;	for(i=2;i<=sqrt(n);i++)	{		if(n%i==0)		{			flag=0;			break;		}	}	return flag;}int main(){	int i,t,reversenum;	for(i=1;i<=9999;i++)	{		reversenum=0;		t=i;		while(t>0)                             //求"反序数"		{			reversenum=reversenum*10+t%10;			t/=10;		}		if(is_Prime(i))                        //i为素数 		{			if(i==reversenum)                  //且i从左向右和从右向左数值相同，输出i 				printf("%d/n",i);		}	}	return 0;}
程序截图：
五、孪生素数
        求出m~n之间（包括m和n）的孪生素数，用（x，x+2）的形式表示
        孪生素数是指：间隔为2的两个相邻素数（如（1,3），（3,5），（11,13）等）
源代码：
#include <stdio.h>#include <math.h>int is_Prime(int n){	int i;	int flag=1;	for(i=2;i<=sqrt(n);i++)	{		if(n%i==0)		{			flag=0;			break;		}	}	return flag;}int main(){	int i,m,n;	while(scanf("%d %d",&m,&n)!=EOF)	for(i=m;i<=n;i++)	{		if(is_Prime(i) && is_Prime(i+2))			printf("(%d,%d)/n",i,i+2);	}	return 0;}程序截图：
六、梅森素数
        求出指数为n（n<20）的所有梅森素数
        梅森素数是指：形如 2^n-1 的正整数，其中指数n是素数，且 2^n-1 也是素数
源代码：
#include <stdio.h>#include <math.h>int is_Prime(int n){	int i;	int flag=1;	for(i=2;i<=sqrt(n);i++)	{		if(n%i==0)		{			flag=0;			break;		}	}	return flag;}int main(){	int i,j,n;	while(scanf("%d",&n)!=EOF)	{		for(i=1;i<=n;i++)		{			j=pow(2,i)-1;			if(is_Prime(i) && is_Prime(j))				printf("pow(2,%d)=%d/n",i,j);		}	}	return 0;}
程序截图：