CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 6 of 6
  1. #1
    Join Date
    Oct 2015
    Posts
    3

    Finding the nth prime number in fibonacci sequence

    I'm supposed to print out the 8th prime number from the fibonacci sequence. I'm stuck on this code, i've been trying for hours but I can't get it right. There is no output. Someone please help me with this code — to get the nth prime number from the fibonacci sequence. I know i'm close I just don't seem to get there.
    Thank you.


    Code:
    #include <iostream>
     using namespace std;
      
     int fibonacci(int n) {
              if ( n == 1 || n == 0 )
                      return n;
      
              int fn = 0;
              int fn1 = 0;
              int fn2 = 1;
              for ( int i = 2; i <= n; i++ ) {
                      fn = fn1 + fn2;
                      fn1 = fn2;
                      fn2 = fn;
               }
     return fn;
     }
    
    bool isPrime (int n) {
    
             int x = 2;
             while (x < n) {
             if (n % x == 0) {
                 return false;
             }
             x++;
             }
    return true;
    }
     
     
     int main() {
                 int n;
                 cout << "Enter a number greater than 1: " << endl;
                cin >> n;
                cout << endl;
                cout<< "The first 8 prime fibonacci numbers are: " ;
    
             for (int primecount = 8; primecount <= 8; primecount --) {
                 for (int x = 3; x >= 3 ; x++){
                     int f = fibonacci (x);
                     if( isPrime (f))
                    cout << f << " ";
                 }
      
             }
             cout << endl;
     return 0;
      }

  2. #2
    Join Date
    May 2001
    Location
    Germany
    Posts
    1,158

    Re: Finding the nth prime number in fibonacci sequence

    The first thing I can spot is that both of your for-loops only end when the loop variable overflows, i.e. primecount is alsways <= 8 until it wraps from -2147483648 to 2147483647 and vice versa for x.

    HTH,
    Richard

  3. #3
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,822

    Re: Finding the nth prime number in fibonacci sequence

    I'm stuck on this code, i've been trying for hours but I can't get it right. There is no output.
    This is when the debugger becomes your friend. Use the debugger to trace through the code and see its flow of execution and the values of the variables. Then you will see when this deviates from that expected from the design.

    print out the 8th prime number from the fibonacci sequence.
    Then why are you asking for a number to be entered that isn't used?

    Your isPrime() function is extremely inefficient. If the number to be tested is even, then it is not a prime. If the number is not even then you don't need to test for division by an even number. ie do one test for being even and then test for odd number division. Also you don't need to increment the divisor past the square root of the number.
    Last edited by 2kaud; October 30th, 2015 at 01:49 PM.
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++23 Compiler: Microsoft VS2022 (17.6.5)

  4. #4
    Join Date
    Jun 2015
    Posts
    208

    Re: Finding the nth prime number in fibonacci sequence

    Quote Originally Posted by 2kaud View Post
    Your isPrime() function is extremely inefficient.
    Also the generation of the Fibonacci numbers is inefficient since each new number is generated from the start. The generation unnecessarily becomes quadratic rather than linear.

    Simplest would be to generate the Fibonacci sequence in a loop and increment a counter for each prime found until 8 is reached and the loop is quit.

  5. #5
    Join Date
    Nov 2015
    Posts
    1

    Re: Finding the nth prime number in fibonacci sequence

    Try this code..

    #include <stdio.h>

    long long fib(long long n)
    {
    if (n <= 2) {
    return 1;
    }
    return fib(n - 2) + fib(n - 1);
    }

    int main(int argc, char ** argv)
    {
    long long result;
    if (argc < 2) {
    fprintf(stderr, "use: fib <n> \n");
    return 0;
    }
    int n = atoi(argv[1]);
    long long i;

    for (i = 0; i <= n; i++) {
    result=fib(i);
    }
    printf(" result= %lld\n", result );

    return 0;
    }



    To execute runs like ./fib X (The X is the nth number that you are looking for)

  6. #6
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,822

    Re: Finding the nth prime number in fibonacci sequence

    When posting code, please use code tags. Go Advanced, select the formatted code and click '#'.

    Obtaining fibonacci numbers via 2 part recursion is extremely inefficient! Consider
    Code:
    unsigned long long fibonacci(unsigned int n)
    {
    	if (n < 2)
    		return n;
    
    	unsigned long long tot = 1;
    
    	for (unsigned int i = 2, cur = 0; i <= n; ++i)
    		cur = (tot += cur) - cur;
    
    	return tot;
    }

    Code:
    if (n <= 2) {
    return 1;
    }
    The first three numbers of a modern fibonacci sequence are 0, 1, 1 (see https://en.wikipedia.org/wiki/Fibonacci_number) so if n is 1 then this will return the incorrect result 1 rather than the expected value of 0.

    Code:
    int n = atoi(argv[1]);
    long long i;
    If n is if type int then it is superfluous to define i (loop index) as type long long as it's maximum value will be that of n which is of type int.

    Code:
    for (i = 0; i <= n; i++) {
    result=fib(i);
    }
    printf(" result= %lld\n", result );
    This loop will execute one too many times as the starting value is 0 not 1. There is no '0th' fibonacci number.

    If you want the nth fibonacci number, then why compute all the previous numbers? If you want the 5th number why compute the 1st, 2nd, 3rd and 4th and then 'throw away' the result? Why not
    Code:
    printf(" result= %lld\n", fib(n));
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++23 Compiler: Microsoft VS2022 (17.6.5)

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured