algorithm - 搜索质数

Question

我希望我没有重复任何问题，但建议的主题没有提供任何类似的问题。我有一个检查数字是否为素数的功能。现在这是搜索素数的最慢方法。

subroutine is_prime_slow(num, stat)
        implicit none
        logical :: stat
        integer :: num
        integer :: i
        if ((num .le. 3) .and. (num .gt. 1)) then
            stat = .true.
            return
        end if

        ! write(*,*) 'limit = ',limit
        do i = 2,num - 1
            ! write(*,*) 'mod(',limit,i,') = ',mod(limit,i)
            if (mod(num,i) == 0) then
                stat = .false.
                return
            end if
        end do
        stat = .true.   
        return     
    end

现在假设我对它做了一些改进。

subroutine is_prime_slow(num, stat)
    implicit none
    logical :: stat
    integer :: num
    integer :: i
    if ((num .le. 3) .and. (num .gt. 1)) then
        stat = .true.
        return
    end if
    ! IMPROVEMENT
    if ((mod(num,2) == 0) .or. (mod(num,3) == 0) .or. (mod(num,5) == 0) .or. (mod(num,7) == 0)) then
        stat = .false.
        return
    end if

    ! write(*,*) 'limit = ',limit
    do i = 2,num - 1
        ! write(*,*) 'mod(',limit,i,') = ',mod(limit,i)
        if (mod(num,i) == 0) then
            stat = .false.
            return
        end if
    end do
    stat = .true.   
    return     
end

现在第二个版本排除了一半以上的数字，例如所有能被 2,3,5,7 整除的。当我用 linux 'time' 程序计时执行时，'改进' 版本的执行速度怎么可能一样慢？我是否遗漏了一些明显的技巧？

Searching the first 900000 numbers:
1st: 4m28sec
2nd  4m26sec

Answer 1

2、3、5 和 7 的倍数无论如何都会很快被原始算法拒绝，因此跳过它们根本不会提高性能。该算法花费大部分时间的地方是证明具有大质因数的数字是合数。要从根本上提高性能，您应该使用更好的 primality test ，例如 Miller-Rabin。

一个更简单的改进是只测试高达 sqrt(num) 的因素，而不是 num-1。如果这没有立即意义，请考虑合数的最小质因数有多大。此外，如果您正在寻找从 1 到 N 的素数，使用素数筛或仅用您已经找到的素数来测试整除性可能更有效。