搜寻含特定因子的第n个数字的高效算法

Program Fcode_cn
! 只有2、3、5因子的数，从小到大排列，第一个数是1，1=2^0*3^0*5^0，求解第1500个数。
! szw_sh@163.com
! 2020-11-11
  Implicit None
  Integer , parameter :: NM = 1500! 经测试，本代码可以计算到至少n=10000
  Integer(kind=8) , parameter :: k(*) = [2,3,5,7]
  Integer(kind=8) :: a(NM), m, t, mi , n , i , j
  a(1) = 1
  n = 1
  Do While (n<NM)
    If (n<20 .or. n>NM-20) Write (*, '(i10.4,a,i9)') n, '  ==>  ', a(n)
    If (n==100) Write (*, *) '    .............' ! 输出部分中间结果。前置的输出，确保n=1时也能输出
    m = a(n)*5 ! 设定n+1的初值，搜索此前项乘以2、3、5后不小于a(n)的最小值
    mi = a(n)/5 + 1 ! 向前搜索的终点值
    Do i = n - 1 + 1/n, 1, -1 ! +1/n，保证n=1时，从1开始递减循环，而不是跳过
      If (a(n)<mi) Exit
      Do j = 1, size(k) ! 搜寻大于a(n)的最小有效值
        t = a(i)*k(j)
        If (t>a(n) .And. t<m) m = t
      End Do
    End Do
    n = n + 1 ! 计数，赋值
    a(n) = m
  End Do
  Write (*, '(/i10.4,a,i9)') 1500, '  ==>  ', a(1500) ! 输出第1500项
End Program Fcode_cn