厄拉多塞筛法求所有小于n的素数

Jackdaw

算法：
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

测试结果：