We have a number $k$ and we have to find the smallest Fibonacci number that has common factor with it(except $1$). We also have $2 \leq k \leq 1,000,000$.
The required Fibonacci number is guaranteed to be less than $10^{18}$.
We have a number $k$ and we have to find the smallest Fibonacci number that has common factor with it(except $1$). We also have $2 \leq k \leq 1,000,000$.
The required Fibonacci number is guaranteed to be less than $10^{18}$.
Find all the primes dividing $k$. Run the Fibonacci recursion modulo each of these primes. See which gives you zero first. For example, if $k=667=23\times29$, the sequence reduced modulo 23 goes $1,1,2,3,5,8,13,21,11,9,20,6,3,9,12,21,10,8,18,3,21,1,22,0$ so the 24th Fibonacci number is a multiple of 23; modulo 29, you get $1,1,2,3,5,8,13,21,5,26,2,28,1,0$ so the 14th Fibonacci is a multiple of 29. $14\lt24$, so the 14th Fibonacci (which is $377=13\times29$) is the first one with a nontrivial common factor with $k$.