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?
题目大意：
我们称197为一个循环质数，因为它的所有轮转形式: 197, 971和719都是质数。
100以下有13个这样的质数: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 和97.
100万以下有多少个循环质数？
//（Problem 35）Circular primes
// Completed on Fri, 26 Jul 2013, 06:17
// Language: C
//
// 版权所有（C）acutus (mail: acutus@126.com)
// 博客地址：http://www.cnblogs.com/acutus/#include<stdio.h>
#include<math.h>
#include<string.h>
#include<ctype.h>
#include<stdlib.h>
#include<stdbool.h> bool isprim(int n)
{
int i=;
for(; i*i<n; i++)
{
if(n%i==) return false;
}
return true;
} bool circular_prime(int n)
{
int i,j,flag=;
char s[];
int sum=;
sprintf(s,"%d",n);
int len=strlen(s);
for(i=; i<len; i++)
{
if(s[i]!='' && s[i]!='' && s[i]!='' && s[i]!='')
return false;
}
for(i=; i<len; i++)
{
for(j=i; j<i+len-; j++)
{
sum+=s[j%len]-'';
sum*=;
}
sum+=s[j%len]-'';
if(!isprim(sum)) return false;
sum=;
}
return true;
} int main()
{
int sum=; //已包含2,3,5,7
for(int i=; i<; i++)
{
if(circular_prime(i))
sum++;
}
printf("%d\n",sum);
return ;
}
|
Answer:
|
55 |