Problem Description
素数筛法是这样的：
1.开一个大的bool型数组prime[]，大小就是n+1就可以了.先把所有的下标为奇数的标为true,下标为偶数（除了2）的标为false.
2.然后：将素数的倍数筛掉
for( i=3; i<=sqrt(n); i+=2 )
{ if(prime[i])
for( j=i+i; j<=n; j+=i ) prime[j]=false;
}
3.最后输出bool数组中的值为true的单元的下标，就是所求的n以内的素数了。
原理很简单，就是当i是质(素)数的时候，i的所有的倍数必然是合数。如果i已经被判断不是质数了，那么再找到i后面的质数来把这个质
数的倍数筛掉。
一个简单的筛素数的过程：n=30。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
第 1 步过后4 ... 28 30这14个单元被标成false,其余为true。
第 2 步开始：
i=3; 由于prime[3]=true, 把prime[6], [9], [12], [15], [18], [21], [24], [27], [30]标为false.
i=4; 由于prime[4]=false,不在继续筛法步骤。
i=5; 由于prime[5]=true, 把prime[10],[15],[20],[25],[30]标为false.
i=6>sqrt(30)算法结束。
第 3 步把prime[]值为true的下标输出来：
for(i=2; i<=30; i++)
if(prime[i]) printf("%d ",i);
结果是 2 3 5 7 11 13 17 19 23 29
#include<stdio.h> bool is[9989900]; //如果i是素数，then is[i]=fasle, else is[i]=true; int prime[1000]; //prime用来存回文素数表 void set()//高效判断素数法:所有和数都等于N个素数的乘积 { int i,j; /*for(i=5;i<=3163;i++) is[i]=0; 由于bool类型默认值是false,所以可以注释掉*/ i=2; for(j=i*i;j<=9989899;j+=i) //偶数，true的不是素数 is[j]=true; for(i=3;i<=3163;i=i+2) { if(is[i]) continue; for(j=i*i;j<=9989899;j+=i) //素数的倍数不是素数 is[j]=true; } } bool test(int a)//判断a是不是回文数 { int temp=a; int b=0; while(temp!=0) //每位倒置，看结果与原数是否一致 { b=b*10; b+=temp%10; temp/=10; } return a==b; } int main() { int a,b; int i,k=0; set(); for(i=5;i<=9989899;i+=2) //将最大范围的所有满足条件的数求出来 if(!is[i]&&test(i)) prime[k++]=i; while(~scanf("%d %d",&a,&b)) //输出给定范文的结果 { for(i=0;i<k;i++) { if(prime[i]<a) continue; else if(prime[i]<=b) printf("%d ",prime[i]); else break; } printf(" "); } return 0; }
方法二： #include <stdio.h> #include <string.h> int huiwen(int k) { int a[10],i=0,j; while (k>0) { a[i]=k%10; k/=10; i++; } for (j=0; j<i; j++) if (a[j]!=a[i-j-1]) return 0; return 1; } int hwlength(int k) { int a[10],i=0; while (k>0) { a[i]=k%10; k/=10; i++; } return (i); } int prime(int k) { int i; for (i=3; i*i<=k; i+=2) if (k%i==0) return 0; return 1; } int main() { int a,b,i,j; scanf("%d%d",&a,&b); for (i=a; i<=b; i++) { if (i%2==0&&i!=2) continue; if (i%5==0&&i!=5) continue; if (hwlength(i)%2==0&&i!=11) continue; if (!huiwen(i)) continue; if (prime(i)) printf("%d ",i); } return 0; }