I just wrote a C program based off this note that can decide whether the Fibonacci number is prime for a prime index . (Recall that is composite when is composite.) I had written a MATLAB code some years back and since I can’t access MATLAB on my current computer I decided to rewrite it in C. The program can compute the smallest prime factor of for all primes on a 64-bit system.

EDIT: I’ve improved my program slightly so that now it works for . (Note: .) The new code looks somewhat ugly so I won’t post it here.

#include <stdio.h> int isprime(unsigned long long n) { int i, ans=1; for (i=2; i*i<=n; i++) { if(n%i==0){ ans=0; break; } } return ans; } int main() { int p; printf("Enter an odd prime number: "); scanf("%d", &p); unsigned long long prev=1, cur=1, next, ind=2; while (ind<p) { next=prev+cur; prev=cur; cur=next; ind++; } unsigned long long Fp, P, Q; Fp=cur; P=4*p+1; Q=2*p-1; while (Q*Q<=Fp) { if (isprime(Q)==1 && ((Q%10)-3)*((Q%10)-7)==0 && Fp%Q==0){ printf("The smallest prime factor of Fibonacci(%d)=%llu is %llu.", p, Fp, Q); return 0; } else if (isprime(P)==1 && ((P%10)-1)*((P%10)-9)==0 && Fp%P==0){ printf("The smallest prime factor of Fibonacci(%d)=%llu is %llu.", p, Fp, P); return 0; } P=P+4*p; Q=Q+4*p; } if (Q*Q>Fp) printf("Fibonacci(%d)=%llu is prime.", p, Fp); return 0; }