厄拉多塞筛法求所有小于n的素数
本帖最后由 Jackdaw 于 2018-11-25 20:53 编辑算法：
1.给定一个数表{2,3,4,……,n}
2.每次从表中删去 2,3,5...等相继素数的倍数，直到最大素数小于等于根号n
代码：
! 厄拉多塞筛法
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
测试结果：
页:
[1]