（Problem 35）Circular primes

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万以下有多少个循环质数？

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<ctype.h>
#include<stdlib.h>
#include<stdbool.h>

bool isprim(int n)
{
	int i=2;
	for(; i*i<n; i++)
	{
		if(n%i==0)  return false;
	}
	return true;
}

bool circular_prime(int n)
{
	int i,j,flag=1;
	char s[6];
	int sum=0;
	sprintf(s,"%d",n);
	int len=strlen(s);
	for(i=0; i<len; i++)
	{
		if(s[i]!='1' && s[i]!='3' && s[i]!='7' && s[i]!='9')
			return false;
	}
	for(i=0; i<len; i++)
	{
		for(j=i; j<i+len-1; j++)
		{
			sum+=s[j%len]-'0';
			sum*=10;
		}
		sum+=s[j%len]-'0';
		if(!isprim(sum)) return false;
		sum=0;
	}
	return true;
}


int main()
{
	int sum=4;    //已包含2,3,5,7
	for(int i=11; i<1000000; i++)
	{
		if(circular_prime(i))   
			sum++;
	}
	printf("%d\n",sum);
	return 0;
}

 

Answer:

55