Fortran Coder

标题: 厄拉多塞筛法求所有小于n的素数 [打印本页]

---

作者: Jackdaw    时间: 2018-4-19 23:55
标题: 厄拉多塞筛法求所有小于n的素数


算法：
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 (89.11 KB, 下载次数: 240)

下载附件

2018-4-19 23:54 上传

---

欢迎光临 Fortran Coder (http://bbs.fcode.cn/)

Powered by Discuz! X3.2