Fortran 中的质数生成器

Question

我只是想稍微熟悉一下 Fortran（因为我可以），所以我编写了这个小程序，它使用埃拉托斯特尼筛法来生成素数。程序如下：

program prime
implicit none
integer num_primes, at, found, i
logical is_prime
integer, allocatable, dimension(:) :: primes ! array that will hold the primes
print *, "How many primes would you like to find?"
read (*, *) num_primes
allocate (primes(num_primes))
primes(1) = 2
at = 2
found = 1
do
    is_prime = .true. ! assume prime
    do i = 1, found
        if (modulo(at, primes(i)) == 0) then ! if divisible by any other element
            is_prime = .false.               ! in the array, then not prime.
            at = at + 1
            continue
        end if
    end do
    found = found + 1
    primes(found) = at
    print *, at
    at = at + 1
    if (found == num_primes) then ! stop when all primes are found
        exit
    endif
end do

end program prime

运行此命令将显示错误是什么，例如，尝试查找 10 个素数将产生以下数字：3, 5, 7, 11, 13, 16, 17, 19, 23。显然16 不是素数。可能出什么问题了？

Answer 1

这不是埃拉托色尼筛法，它不需要模。
这是一种试除法，但是当您找到除数时，您将 at 加 1，并开始测试下一个素数，您应该重新开始。
当您发现 15 可以被 3 整除时，at 会增加到 16，并针对 5、7、11 进行测试，这些当然不是 16 的约数，因此会打印 16。

我不是 FORTRAN 程序员，但我认为您应该将这些行替换

at = at + 1
continue

为

exit

并仅在 is_prime 为 true 时才执行这些行

found = found + 1
primes(found) = at
print *, at

。

Answer 2

这是实现 Henrik 建议的工作程序（然后我做了一些格式更改）：

program prime
implicit none

integer :: num_primes, at, found, i
logical :: is_prime
integer, allocatable, dimension(:) :: primes ! array that will hold the primes

print *, "How many primes would you like to find?"
read(*, *) num_primes
allocate(primes(num_primes))
primes(1) = 2
at = 2
found = 1
do
    is_prime = .true. ! assume prime
    do i = 1, found
        if (modulo(at, primes(i)) == 0) then ! if divisible by any other element
            is_prime = .false.               ! in the array, then not prime.
            exit
        end if
    end do
    if (is_prime) then
        found = found + 1
        primes(found) = at
        print *, at
    end if
    at = at + 1
    if (found == num_primes) then ! stop when all primes are found
        exit
    end if
end do
end program prime

当您运行此程序时，您将得到：

 How many primes would you like to find?
20
           3
           5
           7
          11
          13
          17
          19
          23
          29
          31
          37
          41
          43
          47
          53
          59
          61
          67
          71

并且 primes 数组将包含所有素数。这就是你想要的吗？