Wu Yudong's Blog

Pandigital prime

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once. For example, 2143 is a 4-digit pandigital and is also prime.

What is the largest n-digit pandigital prime that exists?

全数字的素数

如果一个n位数恰好使用了1至n每个数字各一次，我们就称其为全数字的。例如，2143就是一个4位全数字数，同时它恰好也是一个素数。

最大的全数字的素数是多少？

//（Problem 41）Pandigital prime
// Completed on Fri, 26 Jul 2013, 13:01
// Language: C11
//
// 版权所有（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;
	if (n == 1)
		return false;
	for (; i * i <= n; i++) {
		if (n % i == 0)
			return false;
	}
	return true;
}

bool pandigital(int n)
{
	char s[10], d[10] = { 0 };
	int i = 0;
	sprintf(s, "%d", n);
	int len = strlen(s);
	while (i < len) {
		switch (s[i] - '0') {
		case 1:
			d[1] ++;
			break;
		case 2:
			d[2] ++;
			break;
		case 3:
			d[3] ++;
			break;
		case 4:
			d[4] ++;
			break;
		case 5:
			d[5] ++;
			break;
		case 6:
			d[6] ++;
			break;
		case 7:
			d[7] ++;
			break;
		case 8:
			d[8] ++;
			break;
		case 9:
			d[9] ++;
			break;
		default:
			break;
		}
		i++;
	}
	for (i = 1; i <= len; i++) {
		if (d[i] != 1)
			return false;
	}
	if (!isprim(n))
		return false;
	else
		return true;
}

int main()
{
	int i = 10000001;
	while (i > 1000) {
		if (pandigital(i)) {
			printf("%d\n", i);
			break;
		}
		i = i - 2;
	}
	return 0;
}

Answer:7652413

Completed on Fri, 26 Jul 2013, 20:01