Fortran Coder

查看: 5437|回复: 0

[数理统计] 厄拉多塞筛法求所有小于n的素数

[复制链接]

63

帖子

9

主题

0

精华

专家

超凡脱俗

F 币
474 元
贡献
237 点
发表于 2018-4-19 23:55:06 | 显示全部楼层 |阅读模式
本帖最后由 Jackdaw 于 2018-11-25 20:53 编辑

算法:
1.给定一个数表{2,3,4,……,n}
2.每次从表中删去 2,3,5...等相继素数的倍数,直到最大素数小于等于根号n

代码:

[Fortran] 纯文本查看 复制代码
! 厄拉多塞筛法
program main
  implicit none
  integer             :: n
  integer             :: i,pid,cid
  integer,allocatable :: prime(:)

  write(*,"(a)") "# please type a integer number(>1)"
  read (*,*) n

  allocate( prime(1:n-1) )
  forall(i=1:n-1) prime(i) = i

  do pid = 2, int(sqrt(n*1.))
    if( prime(pid) .eq. 0 ) cycle
    do i = pid+1, n-1
      if( prime(i) .eq. 0 ) cycle
      if( mod(prime(i),prime(pid)) .eq. 0 ) prime(i) = 0
    end do
  end do

  write(*,"(a,i5,a)") "# the prime number less than ",n," :"
  cid = 0
  do i = 1,n-1
    if( prime(i) .ne. 0 ) then
      write(*,fmt="(1x,i0)",advance="no") prime(i)
      cid = cid + 1
      if( mod(cid,10) .eq. 0 ) write(*,*)
    end if
  end do
  write(*,*)
  deallocate( prime )
end


测试结果:




无标题.png
天下英雄出我辈,一入江湖岁月催。

鸿图霸业谈笑间,不胜人生一场醉。
您需要登录后才可以回帖 登录 | 极速注册

本版积分规则

捐赠本站|Archiver|关于我们 About Us|小黑屋|Fcode ( 京ICP备18005632-2号 )

GMT+8, 2024-10-10 16:24

Powered by Tencent X3.4

© 2013-2024 Tencent

快速回复 返回顶部 返回列表