alternating Fibonacci and prime series

Question

The task is to print the following series

1 2 1 3 2 5 3 7...

The elements at odd positions are Fibonacci series terms and the elements at even positions are prime numbers. Given an input 'n' the element at the nth position in the series has to be printed. eg. when n = 4, output will be 3. n = 7, output will be 3

I've tried to solve the problem by returning nth prime number or nth fibonacci term. I am looking for any improvements that can be made to the code to optimize it further.

#include <bits/stdc++.h>
using namespace std;


int retPrime(int n)
{
    //Using sieve of Eratosthenes to generate primes 
    int size = n + 1;
    bool Primes[100];
    int count = 0;
    memset(Primes, true, sizeof(Primes));
    for (int i = 2; i<sqrt(100); ++i)
    {
        if (Primes[i] == true)
        {
            for (int j = i * 2; j <= 100; j = j + i)
            {
                Primes[j] = false;
            }
        }
    }
    int primeIndex=0;
    int i = 2;
    while (count != n)
    {
        if (Primes[i] == true)
        {
            count++;
            primeIndex = i;
        }
        ++i;
    }
    return primeIndex;
}

int retFib(int n)
{
    if(n<=1){
        return n;
    }
    return retFib(n-1)+retFib(n-2);
}
int main()
{
    int n;
    cin >> n;
    if(n%2==0)
        cout << retPrime(n/2)<<" ";
    else
        cout << retFib((n/2)+1)<<" ";
    return 0;
}

Answer 1

1. <bits/stdc++.h> is non-standard and likely far more than you actually need. Unless coupled with use of precompiled headers, it will slow down compilation at least. Replace it with the standard includes. See "How does #include <bits/stdc++.h> work in C++?".

2. Never import wholesale any namespace which isn't designed for it. Doing so leads to conflicts, silent changes of behaviour, and generally brittle code. See "Why is “using namespace std” considered bad practice?".

3. Crank up the warning-level for your compiler. You will see it complain that size in retPrime() is unused.

4. There are only two good reason to give a variable a bigger scope than needed: Restricting the scope would be more verbose, or constructing it anew repeatedly would be more expensive. Otherwise, it's needless extra-stress put on each reader to understand things.

5. Avoid magic numbers. Instead, use some well-named constant, or simply eliminate them.

6. std::sqrt() may be required by the IEEE Standard to be exact. But does your implementation guarantee IEEE-conformance? Anyway, why not start with the square-roots?

7. Try to use fewer variables. Instead of incrementing a new variable up to a target, decrement the target if you don't need it any longer.

8. If you detect an error, like running beyond the bounds of your sieve, throw an exception, return an obviously impossible value (0 is a good candidate), or abort the program. But don't return a value which looks legitimate but is wrong.

9. Take a bit more care with formatting. An empty line before each function is a good idea, but please neither more (before the first) nor less (before the last).

10. retFib() and retPrime() are curious names. getFibonacci() and getPrime() seem better.

11. You really should add a function for your own series, abstracting the details away.

12. Comparing booleans against true or false is just pointless verbosity. Use the value directly, or after Negation with !.

13. There is no guarantee that a bool is a byte big. Nor that memsetting every byte to 1 will result in a valid bool, let alone that it's true. Use std::fill, or reverse the logic and use aggregate-initialization to start with all-false instead.

    Even better, consider that the only even prime is 2, and change the code accordingly.

14. Calculating fibonacci naively needs \$O(n)\$ space and \$O(2^n)\$ time. Consider being slightly more clever and calculate it iteratively in \$O(1)\$ space and \$O(n)\$ time.

15. The conditional operator condition ? true_exp : false_exp is excellent for selecting one of two expressions. Use it where appropriate.

16. You should end each line of output with \n, it's expected. A single space instead is surprising.

17. If you want to stream a single character, use a character-literal, not a length-one string-literal. It might be slightly more efficient.

18. return 0; is implicit for main().

19. Use noexcept where appropriate.

20. Don't make things external for no reason. It increases the chance for collisions, and decreases the chance for inlining.

21. Input can fail. Deal with it.

22. As a final point, it might be better to just pre-compute the full sequence and be done with it. That might even save space.

Modified code:

#include <iostream>

static int getPrime(int n) noexcept {
    //Using sieve of Eratosthenes to generate primes
    constexpr auto sqrt_size = 10;
    constexpr auto size = sqrt_size * sqrt_size;
    if (!n) return 2;
    bool prime[size] = {false, false, true};
    for (int i = 3; i < size; i += 2)
        prime[i] = true;
    for (int i = 3; i < sqrt_size; i += 2) {
        if (!prime[i])
            continue;
        if (!--n)
            return i;
        for (int j = i + i; j < size; j += i)
            prime[i] = false;
    }
    for (int i = (sqrt_size & ~1) + 1; i < size; i += 2)
        if (prime[i] && !--n)
            return i;
    return 0;
}

static int getFibonacci(int n) noexcept {
    int last = 0, r = 1;
    while (n-- > 0) {
        int temp = last + r;
        last = r;
        r = temp;
    }
    return r;
}

static int mySeries(int n) noexcept {
    return n % 2 ? getFibonacci(n / 2 + 1) : getPrime(n / 2);
}

int main() {
    int n;
    if (std::cin >> n)
        std::cout << mySeries(n) << '\n';
    else
        std::cerr << "Could not understand your input. Expected a number.\n";
}

Answer 2

Don't use #include <bits/stdc++.h>.

This include is not portable to every compiler and it's non-standard. Also, it includes every standard header which just bloats up the size of your executable. See this relevant Stack Overflow post.

Also, using namespace std; is considered bad practice, since you import the whole namespace. See this other relevant Stack Overflow post.

Consider using std::array <bool,100> instead of a plain C arraybool Primes[100]; It also eliminates the use of memset(Primes, true, sizeof(Primes));. You can just initialise all 100 elements in the array to true.

Instead of if (Primes[i] == true), you can just say if (Primes[i]) for bool types.