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.

Quote:

---

Originally Posted by dbzx

Hey guys,

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 dont know what fibonacci prime is but 19, 31, 37, 41 are all prime. a prime number is one which is completely divisible by 1 and itself only.from this defiintion ur program(if its printing prime numbers) is giving wrong output.(4,22, 26, 34, 38, 46)

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

You'd get a 2x speedup by not calling prime() twice in fibo_prime().

Unless you need to know all of the factors of the number, you should break out of the loop in prime() once you've found the first one.

Using an unsigned int for your calculations on the number will allow you to test one extra number, and it happens to be prime.

Definitely change the code to factor only up to the sqrt of the number you're testing. By only testing factors up to 20, you're missing some of the factors of the larger numbers. This is why you're seeing your program report numbers as prime when they're not. For example F(19) = 4,181 = 37 × 113. By only factoring to 20, you're missing both of those factors.

With these changes, the program tests all of the numbers from 1-47 in less than a tenth of a second on my laptop, and most of the time is spent printing out the results.

If you are interested in pursuing algorithms for solutions to such matters I would highly encourage you to get "Algorithms in C". It addresses this very matter and gives a few solutions on how to effectively calculate prime numbers and emphasizes on what matsp states in top-down dynamic programming or memoization.