首页 > 算法 > 正文

阅读排行

埃氏筛法搜寻1亿以内素数
2018-10-09 17:37:12   来源:Fcode研讨团队   评论:0 点击:

埃氏筛法搜寻1亿以内素数,标记、统计并输出个数和耗时。 网络类似算法不少,但fortran版本未见(至少是中文网站上)。

埃氏筛法搜寻1亿以内素数,标记、统计并输出个数和耗时。网络类似算法不少,但fortran版本未见(至少是中文网站上)。本代码部分减少了重复标记,效率较高。
详见代码注释。


  ! szw_sh@163.com
  ! 2018-10-07
  ! 标记2到1亿所有素数,统计个数
  ! 算法:用埃氏筛法;素数分布特征;部分减少重复标记
  ! 结果:5761455     680 ms
  ! 效率:3.2GHz主频,2G内存,运行时间0.8秒
  ! 编译:FPS4 /Ox ; CVF6 默认选项
Program Main  
  integer(4) :: i,j,k,m,n,d
  integer(4),parameter :: mx=100000000,mx1=mx*1.1
  integer(1) :: a(mx1)      ! mx1拓展数组,防止写溢出
  x=timef()                 ! 计时开始
  a=0                       ! a标记对应下标自然数,1为素数,否则标0
  a(2:3)=1                  ! 2,3 单独标记
  m=2
  n=sqrt(mx*1.0)            ! 搜索到mx平方根。见相关定理                                        
  a(6-1:mx-1:6)=1           ! 以6为步长,初始化标记左右侧为素数
  a(6+1:mx+1:6)=1           ! 6i,6i+2,6i+3,6i+4 等皆为合数  
  do i=6,n,6                ! 以6为步长,搜索素数
    do j=i-1,i+1,2          ! 搜索循环节点的左右2个数
      if(a(j)==0) cycle
      n=j*j
      d=j*2
      do k=n,mx,d           ! 标记搜到的素数的倍数为合数
        if(mod(k,6)==3) exit! 标记从j*j开始,更小的已被前一个素数倍数标记
        a(k)=0              ! 可以j*2为步长,跳过偶数
      end do                ! 遇到余数3时跳出循环,后面只对余数1或5的情形作标记
      n=k+d                 ! 循环标记倍数的起始点
      do k=n,mx,d*3         ! 按照j*2*3步长标记素数的倍数
        if(a(k)/=0) a(k)=0  ! 变化周期为余数5,1,3,省却一次标记动作
        if(a(k+d)/=0) a(k+d)=0! 使用if判断比重复标记更快
      end do
    end do
  end do
  do i=6,mx,6               ! 统计素数个数
    m=m+a(i-1)+a(i+1)
  end do
  n=timef()*1000            ! 计时结束
  write(*,'(1x,2i8,a)') m,n,' ms'! 输出个数,时间
End Program Main

相关热词搜索:素数 筛法 1亿

上一篇:简单数据分割与“打点法”排序
下一篇:搜寻含特定因子的第n个数字的高效算法

分享到: 收藏