学步园

题目连接：uva 10236 - The Fibonacci Primes

题目大意：在给出n，输出第n个为素数的斐波那契数，取数值的前9位数。

解题思路：原本想用打表的方式遍历斐波那契数，然后存在数组了，但是这样判断素数的函数就比较难写，要写成大数，后来看到一条定律，f[n]，如果n为素数，那么f[n]也为素数，所以只要照出素数然后访问斐波那契数列的下标就可以了。

#include <stdio.h>
#include <string.h>
#include <math.h>
const int MAX = pow(10, 9);
const int N = 250005;

int prime[N], cnt;;
double f[N];

void makePrime(int n) {
	int vis[N];
	cnt = 1;
	memset(vis, 0, sizeof(vis));
	for (int i = 2; i * i < n; i++) {
		if (!vis[i]) {
			for (int j = 2 * i; j < n; j += i)
				vis[j] = 1;
		}
	}

	for (int i = 2; i < n; i++)
		if (!vis[i]) prime[cnt++] = i;
}

void init(int n) {
	int flag = 0;
	f[1] = f[2] = 1;
	for (int i = 3; i < n; i++) {
		f[i] = f[i - 1];
		if (flag) f[i] += f[i - 2] / 10;
		else f[i] += f[i - 2];
		flag = 0;
		while (f[i] >= MAX) {
			flag = 1;
			f[i] /= 10;
		}
	}
}

int main () {
	makePrime(N);
	init(N);
	int n;
	while (scanf("%d", &n) == 1) {
		if (n == 1) printf("2\n");
		else if (n == 2) printf("3\n");
		else 
			printf("%d\n", (int)f[prime[n]]);
	}
	return 0;
}