一、基本素數問題回顧

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;}
程序截圖：