首页 > 算法 > 正文

阅读排行

搜寻含特定因子的第n个数字的高效算法
2020-11-12 10:45:10   来源:Fcode研讨团队   评论:0 点击:

只有2、3、5因子的数,从小到大排列,第一个数是1,1=2^0*3^0*5^0,求解第1500个数。 这是一个高效率的算法(1500项仅用25毫秒),在8位整数范围,可以计算到至少第10000项(仅用0 95秒)。

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

相关热词搜索:

上一篇:埃氏筛法搜寻1亿以内素数
下一篇:搜寻所有水仙花数的快速算法

分享到: 收藏