斐波那契数列第1993项的最小质因数是几？

Question

斐波那契数列：
F(1) = 1，F(2) = 1；
F(n) = F(n-1) + F(n-2)，n ≥ 3。
F(1993) 是合数，它的最小质因数是几？

Answer 1

根据网友建议，运用斐波那契矩阵快速幂算法和余数定理。现学现卖，写了一段 fortran 代码。找到 F(1983) 的最小质因数 478321，计算耗时仅 28 毫秒。

---

ai 或借助 ai 都解决不了这类问题。

---

附上代码：

integer*8 a(2),b(2,2)
call cpu_time(x)
do i=1,1000000,2 
  k=max(i,2)
  a=1
  b=1
  b(2,2)=0
  ii=1993-2
  do while(ii.gt.0)
    if(mod(ii,2).eq.1) a=mod(matmul(a,b),k)
    b=mod(matmul(b,b),k)
    ii=ii/2
  end do
  if(a(1).ne.0) cycle
  write(*,'(ag0)') ' prime = ',k
  exit
end do
call cpu_time(x)
write(*,'(ag0a)') ' time = ',int(1000*x),' ms'
end

---

并附在线编译运行的截图：