Find the nth term of a sequence that consists of Fibonacci and prime numbers interleaved

Question

I have given a series problem 1,2,1,3,2,5,3,7,5.... in which the odd terms forms the Fibonacci series and even terms form the prime number series. I have to write a code in which I have to find the nth term. Following is the code for finding the nth term, I want to know whether it can be written more efficiently or not and how?

 def fib(n):
     t1=0
     t2=1
     for i in range(1,n+1):
         add = t1+t2
         t1 = t2
         t2 = add
     print(t1)


 def prime(n):
     count =1
     for i in range(2,100):
         flag =0
         for j in range(2,i):
             if (i%j==0):
                flag=1
                break
         if (flag==1):
             continue
         else:
             if (count==n):
                 print(i)
                 break
             else:
                 count = count+1


 n= int(input('enter the positive number: ' ))

 if (n%2==0):
     prime(int(n/2))
 else:
     fib(int(n/2)+1)

Answer 1

You could use a few tricks to implement the two sequences more efficiently, but the short version of my answer is that most significant performance improvements you could make involve some relatively advanced math, and the smaller improvements do more to improve your code's readability than its performance.

---

Useful improvements to prime

If you keep a list of the primes you find, you only need to check if those divide the new numbers you are checking, rather than checking every number up to the number you are looking at.

You could also skip over even numbers in the outer loop (use range(3, max, 2)), thus avoiding checking even numbers that you can be sure aren't prime (you would need to add a special case for 2).

The inner loop (j) can stop at i/2, because no number can be evenly divided by a number more than half its size. Similarly, you can stop the loop at when you pass the square root of n, but you would have to implement that by squaring the factors because sqrt is limited by the inaccuracy of floating-point numbers.

Using all of these suggestions, the code might look a little like this:

def nth_prime(n):
    if n == 1:
        return 2
    primes = [2]
    for candidate_prime in range(3, MAX, 2):
        for p in primes:
            if (p ** 2 > candidate_prime):
                break # candidate is prime
            if (candidate_prime % p == 0)
                break # p divides candidate; candidate is not prime
        if no primes divided candidate_prime:
            primes.append(candidate_prime)
            if len(primes) == n:
                return candidate_prime

Additional optimizations for determining whether a number is prime are discussed on the Wikipedia page on the subject.

These improvements will only start to have noticeable effects when you start looking at very large primes, so you might also want to use itertools.count to look at all numbers instead of stopping at 100.

(If you really want to stop at 100, you could also just make a list of the prime numbers up to 100 and index that for maximum efficiency.)

---

Links to mathematical solutions

To really improve efficiency, this answer suggests the solution in this blog post, but this is probably overkill unless you really want to be able to calculate very large fibonacci numbers very fast (I can't tell that there's a delay in your function until somewhere far above n=10000).

This question goes into depth about how to find the nth prime number, but the final point is important to note:

tl;dr: Finding the nth prime can be efficiently done, but the more efficient you want it, the more mathematics is involved.

---

Other suggestions

The following suggestions aren't really about efficiency (if they change the efficiency of your code, the difference will be immeasurably small), but they might make your code a little cleaner.

1. In the loop you're using for the Fibonacci sequence, you can just write t1, t2 = t2, t1 + t2 to update both values in one line.

2. When creating the nth Fibonacci number, you can just loop over range(n); there's no need to adjust the ends of the loop. And if you're not using the index i in that loop, Python convention is call it _, so you end up with for _ in range(n).

3. Using Python's less-than-well-known for/else feature might let you eliminate the flag variable. If you put an else block after a loop in Python, it will run only if you do not break out of the loop, which allows you to avoid flag variables.

   for i in some_list:
       if condition(i):
           break
   else:
      do_this_if_condition_was_never_true()
   

Answer 2

I'd take a slightly different approach. Rather than include the n/2 loop in both the Fibonacci and prime code, I'd make it external and turn these two programs into simpler, infinite generators that are easier to debug:

'''
Given a series in which the odd terms forms the Fibonacci series and even
terms form the prime number series, this program finds the nth term.
'''

def fibonacci():
    ''' Generator that continuously yields fibonacci numbers. '''

    a, b = 0, 1

    while True:
        a, b = b, a + b

        yield a

def primes(known_odd_primes=[3]):  # dangerous default value
    ''' Generator that continuously yields prime numbers. '''

    yield 2

    for prime in known_odd_primes:
        yield prime

    odd = known_odd_primes[-1] + 2

    while True:
        for divisor in known_odd_primes:

            if divisor * divisor > odd:
                yield odd
                known_odd_primes.append(odd)
                break

            if odd % divisor == 0:
                break

        odd += 2

def sequence(n):

    '''
    Find nth element of sequence whose odd terms are from the Fibonacci
    series and whose even terms are from the prime number series.
    '''

    if n % 2:
        fibonacci_generator = fibonacci()

        for _ in range(n // 2):
            nth = next(fibonacci_generator)
    else:
        prime_generator = primes()

        for _ in range((n + 1) // 2):
            nth = next(prime_generator)

    return nth

if __name__ == "__main__":
    n = int(input('Enter a positive number: '))

    print(sequence(n))

EXAMPLE:

> python3 test.py
Enter a positive number: 100000
611953
>

Answer 3

This is my first post for suggesting improvements so I may be way off the mark but I think you should

1. Use docstrings in each function and preferably have an overall docstring
2. Use a helper function (in my case find_n_term) so this module can be re-used by other programmers
3. Use the guard if __name__ == "__main__" so others users can import the module and it won't run automatically

"""Problem:
    Odd terms in a sequence are of the Fibonacci series
    Even terms in a sequence are of the prime number series
    e.g:
    1,2,1,3,2,5,3,7,5
    Find the nth term in the series"""


def fib(n):
    """Return the nth fibonacci number"""
    fib_numbers = [1, 1]
    if n in (1, 2):
        return 1
    for i in range(2, n):
        fib_numbers.append(fib_numbers[i - 1] + fib_numbers[i - 2])
    return fib_numbers[-1]


def prime(n):
    """Return the nth prime number"""
    prime_number = 2
    counter = 3
    prime_count = 1
    if n == 1:
        return 2
    while prime_count < n:
        is_prime = True
        for i in range(2, counter):
            if counter % i == 0:
                is_prime = False
                break
        if is_prime:
            prime_count += 1
            prime_number = counter
        counter += 1
    return prime_number


def find_n_term(n):
    """Return the nth term in a sequence where odd terms are from the
    fibonacci sequence and even terms from the primer number sequence"""
    if n % 2 == 0:
        output = prime(n // 2)
        print("Prime number:", output)
    else:
        output = fib((n + 1) // 2)
        print("Fib number:", output)


if __name__ == "__main__":
    for i in range(1,10):
        find_n_term(i)

Answer 4

A tiny improvement to the part that chooses which sequence is required:

 if (n%2==0):
     prime(int(n/2))
 else:
     fib(int(n/2)+1)

Since n is already int, we can use simple integer division:

if n % 2:
    print(fib((n+1)//2)
else:
    print(prime(n//2))

(I've assumed the obvious improvement of making your functions pure, and moving the side-effect to the call site).