素数即只能被自身和1整除的大于1的正整数。
第一个问题是如何判断n是否是素数，可以用所有大于1小于其本身的整数去试着整除该数，若该区间内存在某个数能整除该数则该数不是素数。但其实不需测试到n-1,只需测试到 sqrt(n)+1 即可。原因如下：
假设n存在大于等于sqrt（n)的因数y，则z = n/y必同时为n的因数，且其值小于等于 sqrt(n) 否则 z*y>n
素数判定
题目描述
给定一个数n，要求判断其是否为素数（0,1，负数都是非素数）。
输入描述:
测试数据有多组，每组输入一个数n。
输出描述:
对于每组输入,若是素数则输出yes，否则输入no。
示例1
输入
13
输出
yes
1 #include<stdio.h> 2 #include<math.h> 3 4 int main() 5 { 6 int x,y; 7 int i; 8 int flag; 9 while( scanf("%d",&x)!=EOF) 10 { 11 flag = 1; 12 if( x<=1 ) flag = 0; //小于等于1必不是素数 13 14 else 15 { 16 y = (int)sqrt(x)+1; //开方有可能是小数，强制转换 17 18 for( i=2; i<y; i++) 19 { 20 //这里注意素数从2开始 21 if( x%i==0) 22 { 23 flag = 0; 24 break; 25 } 26 } 27 } 28 if( !flag) printf("no "); 29 else printf("yes "); 30 31 } 32 return 0; 33 }
第二个问题是枚举出一个范围的所有素数。
素数
题目描述
输入一个整数n(2<=n<=10000)，要求输出所有从1到这个整数之间(不包括1和这个整数)个位为1的素数，如果没有则输出-1。
输入描述:
输入有多组数据。 每组一行，输入n。
输出描述:
输出所有从1到这个整数之间(不包括1和这个整数)个位为1的素数(素数之间用空格隔开，最后一个素数后面没有空格)，如果没有则输出-1。
示例1
输入
100
输出
11 31 41 61 71
1 #include <stdio.h> 2 #include <stdlib.h> 3 4 int main() 5 { 6 int n,x; 7 int ans[2000]; //存放目标素数 8 int index; 9 int i; 10 int isPrime,flag; 11 while(scanf("%d",&n)!=EOF) 12 { 13 index = 0; //存放目标素数的个数 14 flag = 1; //解决空格问题 15 for(x = 2 ; x < n ; x++ ) 16 { 17 isPrime = 1; //判断是否是素数 18 for (i = 2; i < x ; i++) 19 { 20 if (x % i ==0) 21 { 22 isPrime = 0; 23 break; 24 } 25 } 26 if (isPrime == 1) 27 { 28 if( x%10 == 1){ 29 //判断尾数是否是1 30 ans[index++] = x; 31 } 32 } 33 } 34 for( i=0; i<index; i++){ 35 if(flag) flag=0; 36 else printf(" "); 37 printf("%d",ans[i]); 38 } 39 } 40 41 return 0; 42 }
再补充一个素数筛选法，即在先筛选出一个范围内素数再做判断，这个速度更快，但是空间要求高
1 #include <stdio.h> 2 #include <stdlib.h> 3 4 void Init( int n); 5 6 int prime[2000]; //保存筛得的素数 7 int primeSize; //保存素数的个数 8 int mark[10001]; //若mark[i]为1，表示其为非素数 9 10 int main() 11 { 12 int n; 13 int i; 14 int flag; 15 while( scanf("%d",&n)!=EOF) 16 { 17 if( n<=1) break; 18 19 flag = 1; 20 Init(n); 21 for( i=0; i<primeSize; i++) 22 { 23 if(prime[i]%10==1) 24 { 25 if( flag ) flag = 0; 26 else printf(" "); 27 printf("%d",prime[i]); 28 } 29 30 } 31 printf(" "); 32 } 33 return 0; 34 } 35 36 void Init( int n) 37 { 38 int i,j; 39 for ( i=1; i<n; i++) 40 { 41 mark[i] = 0; //初始化所有的数字均没有被标记 42 } 43 primeSize = 0; 44 for( i=2; i<n; i++) 45 { 46 if( mark[i]==1) continue; //若已被标记则跳过 47 prime[primeSize++] = i; //否则新得到一个素数 48 for( j=i*i; j<n; j+=i) //将素数的倍数标记为非素数 49 { 50 mark[j] = 1; 51 } 52 } 53 }