搜索素数

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的倍数,因此跳过它们并不能提高性能.算法花费大部分时间的地方在于证明具有大素数因子的数字是复合的.要从根本上改善性能,您应该使用更好的素性测试,例如Miller-Rabin.

一个更简单的改进是测试因素sqrt(num),但不是num-1.如果这没有立即意义,请考虑复合数的最小素因子有多大.此外,如果您正在寻找从1到N的素数,使用素数筛可能更有效,或者仅通过您已经找到的素数来测试可分性.