fibonacci prime

This is a discussion on fibonacci prime within the C Programming forums, part of the General Programming Boards category; Hey guys, My program basically accepts an index(less than 46) and determine whether it's fibonacci number is prime or not ...

  1. #1
    Registered User
    Join Date
    Apr 2009
    Posts
    23

    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;
        }
    }
    Last edited by dbzx; 04-16-2009 at 07:59 PM.

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Who said computing was instant? It gives you your answer, there you go.


    Quzah.
    Hope is the first step on the road to disappointment.

  3. #3
    DESTINY BEN10's Avatar
    Join Date
    Jul 2008
    Location
    in front of my computer
    Posts
    804
    Quote Originally Posted by dbzx View Post
    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)

  4. #4
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  5. #5
    Registered User
    Join Date
    Mar 2009
    Posts
    344
    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.

  6. #6
    Registered User slingerland3g's Avatar
    Join Date
    Jan 2008
    Location
    Seattle
    Posts
    603
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Calculating prime factor of a huge number.
    By Bakster in forum C Programming
    Replies: 15
    Last Post: 02-20-2009, 12:06 PM
  2. prime number program with function
    By mackieinva in forum C Programming
    Replies: 17
    Last Post: 09-20-2007, 09:36 AM
  3. prime numbers, counters, help!
    By vege^ in forum C++ Programming
    Replies: 1
    Last Post: 03-10-2003, 04:32 PM
  4. Prime Wonder
    By vasanth in forum A Brief History of Cprogramming.com
    Replies: 2
    Last Post: 10-08-2002, 12:49 AM
  5. Homework help
    By Jigsaw in forum C++ Programming
    Replies: 2
    Last Post: 03-06-2002, 05:56 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21