Prime fibonacci combinations program in python

Prime Fibonnaci Problem Description Given two numbers n1 and n2

1. Find prime numbers between n1 and n2, then

2. Make all possible unique combinations of numbers from the prime numbers list you found in step 1.

3. From this new list, again find all prime numbers.

4. Find smallest (a) and largest (b) number from the 2nd generated list, also count of this list.

5. Consider smallest and largest number as the 1st and 2nd number to generate Fibonacci series respectively till the count (number of primes in the 2nd list).

6. Print the last number of a Fibonacci series as an output

Constraints 2 <= n1, n2 <= 100

n2 - n1 >= 35

Input Format One line containing two space separated integers n1 and n2.

Output Last number of a generated Fibonacci series.

Timeout 1

Test Case Example 1

Input

2 40

Output

13158006689

Explanation

1st prime list = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]

Combination of all the primes = [23, 25, 27, 211, 213, 217, 219, 223, 229, 231, 32, 35, 37, 311, 313, 319, 323, 329, 331, 337, 52, 53, 57, 511, 513, 517, 519, 523, 529, 531, 537, 72, 73, 75, 711, 713, 717, 719, 723, 729, 731, 737, 112, 113, 115, 117, 1113, 1117, 1119, 1123, 1129, 1131, 1137, 132, 133, 135, 137, 1311, 1317, 1319, 1323, 1329, 1331, 1337, 172, 173, 175, 177, 1711, 1713, 1719, 1723, 1729, 1731, 1737, 192, 193, 195, 197, 1911, 1913, 1917, 1923, 1929, 1931, 1937, 232, 233, 235, 237, 2311, 2313, 2317, 2319, 2329, 2331, 2337, 292, 293, 295, 297, 2911, 2913, 2917, 2919, 2923, 2931, 2937, 312, 315, 317, 3111, 3113, 3117, 3119, 3123, 3129, 3137, 372, 373, 375, 377, 3711, 3713, 3717, 3719, 3723, 3729, 3731]

2nd prime list=[193, 3137, 197, 2311, 3719, 73, 137, 331, 523, 1931, 719, 337, 211, 23, 1117, 223, 1123, 229, 37, 293, 2917, 1319, 1129, 233, 173, 3119, 113, 53, 373, 311, 313, 1913, 1723, 317]

smallest (a) = 23

largest (b) = 3719

Therefore, the last number of a Fibonacci series i.e. 34th Fibonacci number in the series that has 23 and 3719 as the first 2 numbers is 13158006689

Example 2

Input

30 70

Output

2027041

Explanation

1st prime list=[31, 37, 41, 43, 47, 53, 59, 61, 67]

2nd prime list generated form combination of 1st prime list = [3137, 5953, 5347, 6761, 3761, 4337, 6737, 6131, 3767, 4759, 4153, 3167, 4159, 6143]

smallest prime in 2nd list=3137 largest prime in 2nd list=6761

Therefore, the last number of a Fibonacci series i.e. 14th Fibonacci number in the series that has 3137 and 6761 as the first 2 numbers is 2027041

from itertools import permutations
def isPrime(n):
    for i in range(2,n):
        if n%i==0:
            return False
    else:
        return True
def listPrime(n1,n2):
    lis=[]
    for ele in range(n1,n2+1):
        if isPrime(ele)==True:
            lis.append(ele)
    return lis

def returnPrime(lis):
    r=[]
    for ele in lis:
        if isPrime(ele)==True:
            r.append(ele)
    return r

def fibo(mi,ma,c):
    f=mi
    s=ma
    res=[]
    res.append(f)
    res.append(s)
    for i in range(2,c):
        next=f+s  
        res.append(next)
        f,s=s,next
    return res[-1]

def main(n1,n2):
    primeNo=listPrime(n1,n2)
    comb=permutations(primeNo,2)
    r=[]
    for ele in comb:
        r.append(int(str(ele[0])+str(ele[1])))
    comb2=returnPrime(r)
    count=len(comb2)
    mini=min(comb2)
    maxi=max(com2)
    res=fibo(mini,maxi,count)
    return res


if __name__=="__main__":
    lis=list(map(int,input().split()))
    lis[0]=n1
    lis[1]=n2
    res=main(n1,n2)
    print(res)

Please help me write the right solution to the code Also help me optimize it so it runs in below 1 seconds

Given two numbers N1 and N2.

Input:  N1=2, N2 = 40
Output: 13158006689
Explanation:
First prime list = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]

Combination of all the primes = [23, 25, 27, 211, 213, 217, 219, 223, 229, 231, 32, 35, 37, 311, 313, 319, 323, 329, 331, 337, 52, 53, 57, 511, 513, 517, 519, 523, 529, 531, 537, 72, 73, 75, 711, 713, 717, 719, 723, 729, 731, 737, 112, 113, 115, 117, 1113, 1117, 1119, 1123, 1129, 1131, 1137, 132, 133, 135, 137, 1311, 1317, 1319, 1323, 1329, 1331, 1337, 172, 173, 175, 177, 1711, 1713, 1719, 1723, 1729, 1731, 1737, 192, 193, 195, 197, 1911, 1913, 1917, 1923, 1929, 1931, 1937, 232, 233, 235, 237, 2311, 2313, 2317, 2319, 2329, 2331, 2337, 292, 293, 295, 297, 2911, 2913, 2917, 2919, 2923, 2931, 2937, 312, 315, 317, 3111, 3113, 3117, 3119, 3123, 3129, 3137, 372, 373, 375, 377, 3711, 3713, 3717, 3719, 3723, 3729, 3731]

Second prime list=[193, 3137, 197, 2311, 3719, 73, 137, 331, 523, 1931, 719, 337, 211, 23, 1117, 223, 1123, 229, 37, 293, 2917, 1319, 1129, 233, 173, 3119, 113, 53, 373, 311, 313, 1913, 1723, 317]

smallest (A) = 23

largest (B) = 3719
Therefore, the last number of a Fibonacci series i.e. 34th Fibonacci number in the series that has 23 and 3719 as the first 2 numbers is 13158006689

Input: N1 = 30, N2 = 70
Output: 2027041
Explanation:

First prime list = [31, 37, 41, 43, 47, 53, 59, 61, 67]

Second prime list generated form combination of 1st prime list = [3137, 5953, 5347, 6761, 3761, 4337, 6737, 6131, 3767, 4759, 4153, 3167, 4159, 6143]
Smallest prime in 2nd list=3137
Largest prime in 2nd list=6761
Therefore, the last number of a Fibonacci series i.e. 14th Fibonacci number in the series that has 3137 and 6761 as the first 2 numbers is 2027041

Approach: The idea is to use Sieve of Eratosthenes to check that a particular number is a prime number or not in O(1) time. Therefore, Iterate over all the numbers from N1 to N2 and store all the prime numbers in that range in an array, and then using Nested Loop find all unique possible combinations of the prime numbers. Finally, find the prime numbers from all the combination and then the minimum and the maximum of those prime numbers. Using the minimum and the maximum prime numbers we can generate the Fibonacci series to compute the last term (Number of prime numbers in all the combinations) of the Fibonacci series.

How do you print prime numbers in Fibonacci sequence?

How many prime numbers are in the first 10 numbers of the Fibonacci sequence?

Is prime () in Python?