Fabonacci数列定义为(1,1,2,3,5,8,…..),即每个元素是前两个元素的和。如果一个Fabonacci数与所有小于它的Fabonacci数互质,那么称之为Fabonacci质数。现在求第k个Fabonacci质数是第几个Fabonacci数。
\#include "stdafx.h"\
bool IsPrime( const vector\<long\> &fibonacciSeq, int num ){\
bool retVal = true;\
for( vector\<long\>::const\_iterator iter = fibonacciSeq.begin(); iter != fibonacciSeq.end(); iter++ )\
if( num%\*iter == 0 ){\
retVal = false;\
break;\
}\
\
return retVal;\
}\
\
long KthPrimeInFibonacci( int k ){\
if( k \<= 0 ) return 0;\
if( k == 1 ) return 3;\
\
long fnminus1 = 2;\
long fnminus2 = 1;\
long fn = 3;\
int cnt, nth;\
vector\<long\> fibonacciSeq;\
for( cnt = 1, nth = 3; cnt \< k; nth++ ){\
fn = fnminus1 + fnminus2;\
\
fibonacciSeq.push\_back( fnminus1 );\
// 剪枝,除2外的偶数都不是质数.\
if( (fn&0x01) != 0 && IsPrime( fibonacciSeq, fn) ) cnt++;\
\
fnminus2 = fnminus1;\
fnminus1 = fn;\
}\
\
return nth;\
}\
int main(){\
int k;\
while( cin \>\> k )\
cout \<\< KthPrimeInFibonacci( k ) \<\< endl;\
}\
/\*\
1\
3\
\
2\
4\
\
3\
5\
\
4\
7\
\
5\
11\
\
6\
13\
\*/