UVa 10236 The Fibonacci Primes (斐波那契素数) - c++编程基础

注意此题的描述和维基百科上Fibonacci Prime的描述不同。

上面加着重符的文字说明：可以用类似素数筛的方式筛出Fibonacci Prime。

但是，定理“若b|a，则fb|fa”并不能推出“若p是质数，则fp是Fibonacci Prime”。

要证明这一点，我们可以证明“若fb|fa，则b|a”（详见《具体数学》P247及《Proofs that Really Count: The Art of Combinatorial Proof》P12）

完整代码：

/*0.022s*/  
  
#include  
const int maxn = 249450;  
  
int fp[22001];  
bool vis[maxn];  
  
int main()  
{  
    long long a = 0, b = 1, tmp, i, j;  
    int n, cp;  
    for (cp = 1, i = 2; cp < 22001; ++i)  
    {  
        tmp = a + b, a = b, b = tmp;  
        if (b >




= 1e18) b /= 10, a /= 10;  
        if (!vis[i])  
        {  
            tmp = b;  
            while (tmp >= 1e9) tmp /= 10;  
            fp[cp++] = tmp;  
            for (j = i * i; j < maxn; j += i) vis[j] = true;  
        }  
    }  
    //printf("%lld\n",i);  
    fp[1] = 2, fp[2] = 3;  
    while (~scanf("%d", &n))  
        printf("%d\n", fp[n]);  
    return 0;  
}