The Fibonacci number sequence is 1, 1, 2, 3, 5, 8, 13 and so on. You can see that except the first two numbers the others are summation of their previous two numbers. A Fibonacci Prime is a Fibonacci number which is relatively prime to all the smaller Fibonacci numbers. First such Fibonacci Prime is 2, the second one is 3, the third one is 5, the fourth one is 13 and so on. Given the serial of a Fibonacci Prime you will have to print the first nine digits of it. If the number has less than nine digits then print all the digits.
Input
The input file contains several lines of input. Each line contains an integer N (0 < N ≤ 22000) which indicates the serial of a Fibonacci Prime. Input is terminated by End of File.
Output
For each line of input produce one line of output which contains at most nine digits according to the problem statement.
Sample Input
1
2
3
Sample Output
2
3
5
问题链接：UVA10236 The Fibonacci Primes
问题简述：（略）
问题分析：素数和数列计算问题，不解释。
程序说明：（略）
参考链接：（略）
题记：（略）
AC的C++语言程序如下：
/* UVA10236 The Fibonacci Primes */
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
// 欧拉筛法
const int N = 300000; // 第22000个素数其最大值应该不会超过300000
bool isprime[N + 1];
int prime[N / 3], pcnt = 0;
void eulersieve(void)
{
memset(isprime, true, sizeof(isprime));
isprime[0] = isprime[1] = false;
for(int i = 2; i <= N; i++) {
if(isprime[i])
prime[pcnt++] = i;
for(int j = 0; j < pcnt && i * prime[j] <= N; j++) { //筛选
isprime[i * prime[j]] = false;
if(i % prime[j] == 0) break;
}
}
}
const int M = 1e9;
double f[N];
int main()
{
eulersieve();
//打表斐波那契数列
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] >= M) {
flag = 1;
f[i] /= 10;
}
}
int n;
while (~scanf("%d",&n))
if (n == 1)
printf("2\n");
else if(n == 2)
printf("3\n");
else
printf("%d\n", (int)f[prime[n - 1]]);
return 0;
}
