Thread: fibonacci prime

Hey guys,

My program basically accepts an index(less than 46) and determine whether it's fibonacci number is prime or not . i am basically done with my program which determine whether the but its not returning the right output. I tried debugging to see if the fibonacci number is correct and it is. i really dont know whats wrong.

Here are indexes known to be prime: 3, 4, 5, 7, 11, 13, 17, 23, 29, 43
some sites suggests that 19, 31, 37, 41 are primes as well but that I do not know.

My program tells me these indexes are prime: 3, 4, 5, 7, 11, 13, 17, 19, 22, 23, 26, 29, 31, 34, 37, 38, 41, 43, 46

I also tried changing the divisor instead of from (2 - 20) to (2 - input), but then it returns the answer VERY SLOW for very large indexes. Please find the problem. Thanks in advance

Heres the code

Code:

#include <stdio.h>

int fibo(int n);

int fibo_prime(int n);

int prime(int n);

int main()
{
    int n;
    int result;

    printf("Enter a positive integer as Fibonacci index(less than 46): ");
    scanf("%d", &n);

    result = fibo_prime(n);
    if (result == 0)
        printf("Fibonacci index %d will not result in a Fibonacci prime!\n", n);
    else //if (result == 1)
        printf("Fibonacci index %d will result in a Fibonacci prime!\n", n);
}

int fibo_prime(int n)
{
    int fibo_number;

    fibo_number = fibo(n);
    prime(fibo_number);

    return prime(fibo_number);
}

int fibo(int n)
{
    int fib_a, fib_b, result, temp, i;
    temp = 0;

    if (n == 0)
       result = 0;

    else if (n == 1)
         result = 1;
    else
    {
        fib_a = 0;
        fib_b = 1;
        for (i = 2; i <= n; i++) {
            temp = fib_a;
            fib_a = fib_b;
            fib_b = temp + fib_a;
            result = fib_b;
        }
    }
    return result;
}
int prime(int n)
{
    int divisor;
    int prime = 1; //Assume the number is prime

    if (n == 1)
        return 0;
    else {

        for (divisor = 2; divisor <= 20; divisor++) { //for divsior between 2 - input
                if (((n%divisor) == 0) &&(n != divisor))// TEST number if its prime or not
                                        prime = 0;
        }

        if (prime)
                return 1;
        else
                return 0;
    }
}

Who said computing was instant? It gives you your answer, there you go.


Quzah.

You could speed it up quite a bit:
1. Do not calculate the whole sequence of fibonacci numbers every time - since you can just as well keep a table of them ones you have found so far. Only if the table entry is zero do you need to calculate it (and since that number consists of two already known fibonacci numbers, it should not take at all long to figure those out). This should give you a 10x or so improvement on calculating your fibonacci series.

2. You can literally half the time it takes to check if it's a prime by dividing by 2 separately, then divide by all 3, 5, 7 etc using divisor +=2 - if a number is not divisible by 2, it also can't be divided by 4, 6, 8, 10, 12, etc. You would also benefit on the smaller numbers by takign square root of the input number, and using that as a limit, rather than 20 - for numbers under 400 you save a number of iterations.

Code:

        if (prime)
                return 1;
        else
                return 0;

How about "return prime" instead - makes four lines into one much simpler line.

--
Mats