Fortran Coder

查看: 258|回复: 0

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

[复制链接]

38

帖子

5

主题

0

精华

熟手

超凡脱俗

F 币
250 元
贡献
144 点
发表于 2018-4-19 23:55:06 | 显示全部楼层 |阅读模式
算法:
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=2:n) prime(i) = i

  do pid = 1, 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,i5)",advance="no") prime(i)
      cid = cid + 1
      if( mod(cid,10) .eq. 0 ) write(*,*)
    end if
  end do
  write(*,*)
  deallocate( prime )
end


测试结果:




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

鸿图霸业谈笑间,不胜人生一场醉。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 极速注册

本版积分规则

QQ|捐赠本站|Archiver|关于我们 About Us|群聊|Fcode

GMT+8, 2018-9-26 11:28

Powered by Discuz! X3.2

© 2001-2017 Comsenz Inc.

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