Just Fibonacci#192

Just Fibonacci (Editorial)

Written By : MathModel

The main idea of the problem is to brute force , notice that constraints are small so we can brute force the first $50$ fibonacci integers and check if each of them is prime in $O (n f_{i})$ \mathcal{O}(n\sqrt{f_i}) which is roughly $O (n 1. 6^{m a x (n)})$ \mathcal{O}(n\sqrt{1.6^{\max(n)}}) we've $max (n) = 50$ \max(n)=50 thus overall computation upper bound is $O (50 \times 1. 6^{25})$ \mathcal{O}(50 \times 1.6^{25}) which is roughly $6 \times 1 0^{6}$ 6 \times 10^6

It's in fact much better than this , but This is intended in order to convince you that it's doable , we can compute the sum of number of iterations of factorization and end up with $\sum = 81887$ \sum=81887 which is roughly one tenth of the upper bound we got ! , which is very fine as well.

Complexity $O (1. 6^{m a x (n)})$ \mathcal{O}(\sqrt{1.6^{\max(n)}}).

def prime(x):
    if(x==1):return 0
    for i in range(2,int(x**(0.5))+1):
        if(x%i==0):
            return 0
    return 1

n=int(input())

f=[1,1]

for i in range(50):
    f.append(f[-1]+f[-2])
    
ans=[]
for i in f:
    if(prime(i)):
        ans.append(i)

print(ans[n-1])

Python