USACO/pprime

liluvu 2013-12-26

展开全文

Translate:USACO/pprime

Prime Palindromes 回文质数

[编辑]描述

因为151既是一个质数又是一个回文数(从左到右和从右到左是看一样的)，所以 151 是回文质数。

写一个程序来找出范围[a,b](5 <= a < b <= 100,000,000)( 一亿)间的所有回文质数;

[编辑]格式

PROGRAM NAME: pprime

INPUT FORMAT:

(file pprime.in)

第 1 行: 二个整数 a 和 b .

OUTPUT FORMAT:

(file pprime.out)

输出一个回文质数的列表，一行一个。

[编辑]SAMPLE INPUT

5 500

[编辑]SAMPLE OUTPUT

[编辑]提示 HINTS(小心使用 use them carefully!)

Hint 1: Generate the palindromes and see if they are prime. 提示 1: 找出所有的回文数再判断它们是不是质数（素数）.

Hint 2: Generate palindromes by combining digits properly. You might need more than one of the loops like below. 提示 2: 要产生正确的回文数，你可能需要几个像下面这样的循环。

产生长度为5的回文数: C++:

 for (d1 = 1; d1 <= 9; d1+=2) {	// 只有奇数才会是素数
     for (d2 = 0; d2 <= 9; d2++) {
         for (d3 = 0; d3 <= 9; d3++) {
           palindrome = 10000*d1 + 1000*d2 +100*d3 + 10*d2 + d1;//(处理回文数...)
         }
     }
 }
/*
ID: liluvu1
LANG: C++
TASK: pprime
*/

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

int num[9];

int palNumber(int n){
	int s, e;
	s = 0;
	e = n-1;

	int tmp[9];

	memcpy(tmp, num, 9*sizeof(int));
	while (s <= e){
		tmp[e--] = tmp[s++];
	}

	int sum = 0;
	int mul = 1;
	for (int i = n-1; i >= 0; i--){
		sum += tmp[i]*mul; 
		mul *= 10;
	}

	return sum;
}

int isPrime(int n){
	int s = sqrt((double)n);
	for (int i = 2; i <= s; i++){
		if (n % i == 0)
			return false;
	}
	return true;
}

void solve(int n, int min, int max, FILE *fout){
	int c = (n+1)/2;

	int i = 0;
	int j = 0;
	int pal = 0;
	while (i >= 0) {
		if (i == 0)
			j++;
		num[i] = j;

		if (i < c-1){
			i++;
			j = 0;
		} else {
			pal = palNumber(n);
			if (pal >= min && pal <= max && isPrime(pal)){
				fprintf(fout, "%d\n", pal);
			}

			j++;
			while (j > 9) {
				i--;
				j = num[i]+1;
			}
		}
	}
}

int digit(int n){
	int i = 1;
	while (n/10) {
		i++;
		n /= 10;
	}
	return i;
}

int main(){
	FILE *fin = NULL;
	FILE *fout = NULL;

	fin = fopen("pprime.in", "r");
	fout = fopen("pprime.out", "w");

	int min, max;
	fscanf(fin, "%d %d\n", &min, &max);
	
	int s = digit(min);
	int e = digit(max);

	for (int i = s; i <= e; i++) {
		solve(i, min, max, fout);
	}

	return 0;
}