Wu Yudong's Blog

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的圆周素数有十三个：2、3、5、7、11、13、17、31、37、71、73、79和97。

小于一百万的圆周素数有多少个？

//（Problem 35）Circular primes
// Completed on Fri, 26 Jul 2013, 06:17
// Language: C
//
// 版权所有（C）wu yudong
// 博客地址：http://www.wuyudong.com
#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

Completed on Fri, 26 Jul 2013, 13:17