フィボナッチ素数

フィボナッチ素数とは素数の中で\(F_{n+2}=F_{n+1}+F_{n}\)で定義される数列に含まれているような数のことです。

通常\(F_0=0,F_1=1\)としたもので考えます。

ああ、きたないコードだ。

#include <stdio.h>
#include <math.h>
#define N 50
#define STEP 10
#define REPEAT N/STEP
int prime(unsigned int x);
main()
{
	unsigned int fib[N]={0};
	int i,j,count[REPEAT]={0};
	fib[0]=0;
	fib[1]=1;
	for(i=0;i<N;i++){
		fib[i+2]=fib[i+1]+fib[i];
	}

	for(i=0;i<REPEAT;i++){
		for(j=i*STEP;j<(i+1)*STEP;j++){
			count[i]+=prime(fib[j]);
			if(prime(fib[j])){
				printf("fib[%d]=%u\n",j,fib[j]);
			}
		}
		printf("%d-%d of primes:%d\n",i*STEP,(i+1)*STEP-1,count[i]);
	}

    

}

int prime(unsigned int x){
	unsigned int l=(unsigned int)sqrt(x);
	unsigned int i;
	if (x==0||x==1){
		return 0;
	}
	for(i=2;i<=l;i++){
		if(x%i==0){
			return 0;
		}
	}
    return 1;
}

で、結果はこんな感じ。

fib[3]=2
fib[4]=3
fib[5]=5
fib[7]=13
0-9 of primes:4
fib[11]=89
fib[13]=233
fib[17]=1597
10-19 of primes:3
fib[23]=28657
fib[29]=514229
20-29 of primes:2
30-39 of primes:0
fib[43]=433494437
fib[47]=2971215073
40-49 of primes:2

\(F_0=0,F_1=1\)とした場合、素数であるようなフィボナッチ数の項番号も\(4\)を除いて素数になっているというのも面白いです。