Project Euler——Problem 35

daybreakcx posted @ 2009年8月17日 00:07 in Prject Euler , 1308 阅读

原题与答案：

Problem 35

17 January 2003

The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.

There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.

How many circular primes are there below one million?

Answer:55

分析与解答：

这个题目是求1000000以内所有循环本身都是素数的数的个数，比如197循环本身就有197,971和719三个。这个题目最早的时候想要优化一下，避免重复求解，即既然循环一圈都是素数，那么求过的就一起在最小的那个算掉，不用重复求解了。但是这样计算有一个问题，算出的结果都是56，错误就在于11这个数，11自循环后就是本身，这里重复累计了一次，后来用最为朴素的算法得出了55才发现错在哪里，朴素的算法就是一个个素数去枚举，然后累加和，程序非常简单，关键就在打素数表，具体的实现源程序代码如下：

#include<stdio.h>
#include<string.h>
bool nprime[1000001];
int i,j,a[80000],ans;
int check(int s)
{
int i,j,k,cnt=0;
for (i=1,j=10;s>=j;i++,j*=10);
for (j/=10,k=1;k<i;k++)
{
s=(s%j)*10+s/j;
if (!nprime[s])
cnt++;
}
return cnt==i-1;
}
int main()
{
a[0]=0;
memset(nprime,false,sizeof(nprime));
for (i=2;i<=1000000;i++)
if (!nprime[i])
{
a[++a[0]]=i;
if (i<=1000)
for (j=i*i;j<=1000000;j+=i)
nprime[j]=true;
}
ans=0;
for (i=1;i<=a[0];i++)
if (check(a[i]))
ans++;
printf("%d\n",ans);
return 0;
}