Project Euler——Problem 35 - Daybreakcx's Blog - Keep Programming! With Algorithm! With Fun!
Project Euler——Problem 34

Project Euler——Problem 35

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

原题与答案:

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才发现错在哪里,朴素的算法就是一个个素数去枚举,然后累加和,程序非常简单,关键就在打素数表,具体的实现源程序代码如下:

 

  1. #include<stdio.h>
  2. #include<string.h>
  3. bool nprime[1000001];
  4. int i,j,a[80000],ans;
  5. int check(int s)
  6. {
  7.         int i,j,k,cnt=0;
  8.         for (i=1,j=10;s>=j;i++,j*=10);
  9.         for (j/=10,k=1;k<i;k++)
  10.         {
  11.                 s=(s%j)*10+s/j;
  12.                 if (!nprime[s])
  13.                         cnt++;
  14.         }
  15.         return cnt==i-1;
  16. }
  17. int main()
  18. {
  19.         a[0]=0;
  20.         memset(nprime,false,sizeof(nprime));
  21.         for (i=2;i<=1000000;i++)
  22.                 if (!nprime[i])
  23.                 {
  24.                         a[++a[0]]=i;
  25.                         if (i<=1000)
  26.                                 for (j=i*i;j<=1000000;j+=i)
  27.                                         nprime[j]=true;
  28.                 }
  29.         ans=0;
  30.         for (i=1;i<=a[0];i++)
  31.                 if (check(a[i]))
  32.                         ans++;
  33.         printf("%d\n",ans);
  34.         return 0;
  35. }

 

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter