PROBLEM: PRIME FIBONACCI
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
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
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
SOLUTION:
import numpy as np
from array import *
e = list(map(str, input().split(" ")))
arr = np.array(e)
n1 = int(arr[0])
n2= int(arr[1])
prime = array('i')
p=0
if n1>=2 and n2 <=100 and (n2-n1)>=35:
for j in range(n1,n2):
for i in range(2,j):
if(j%i)==0:
break
else:
if j in prime:
pass
else:
prime.insert(p, j)
p += 1
rev = 0
array2 = []
for i in prime:
val = i
for j in prime:
val2 = j
if val == val2:
continue
else:
if val2<= 10:
array2.append((val*10)+val2)
else:
while (val2 > 0):
dig = val2 % 10
rev = rev * 10 + dig
val2 = val2 // 10
while rev!=0:
rem=int(rev%10)
val = int((val*10)+rem)
rev=int(rev/10)
array2.append(val)
val =i
rem = 0
rev = 0
val2 =0
del prime[0:len(prime)]
p = 0
for j in array2:
for i in range(2,j):
if(j%i)==0:
break
else:
if j in prime:
pass
else:
prime.insert(p, j)
p += 1
smallest = prime[0]
largest = prime[0]
for i in prime:
if smallest>i:
smallest = i
elif largest < i:
largest = i
else: continuel
res = int(0)
m = np.zeros(len(prime), dtype='int64')
m[0] = smallest
m[1] = largest
for i in range(2, len(prime) , 1):
m[i] = m[i - 1] + m[i - 2]
res = m[i]
print(res)
Comments