搜索素數

我希望我不會重複任何問題，但建議的主題沒有提供任何類似的問題。我有一個函數來檢查數字是否是主要數字。現在，這是搜索素數最慢的方法。搜索素數

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

來源

2013-09-22 Andro

你只需要檢查_sqrt（num）_（鍛鍊：證明它）的素數除數。要加速：首先使用篩子找到範圍_ [2，sqrt（num）] _中的所有素數，然後在這些素數中搜索除數。如果沒有找到，_num_是主要的。你的代碼速度很慢，原因是：你的_mod_沒有幫助，因爲你的方法對素數很慢，而你的_mod_檢查只加快了複合數字的代碼速度。 – Haile

我知道[2，sqrt（num）]會加快速度。但讓我們說我正在檢查數字2311（首要）和2312（不是首要）。 Sqrt（2311）爲48.073，sqrt（2312）爲48.083。在發言之後，兩者都是48.我不是在搜索相同的兩組數字，即發現它們既不是總數也不是總數？ – Andro

一方面，如果你發現2311不能被2到48中的任何數字整除，你就證明它是素數。另一方面，2312可以被2整除，所以你會發現它是立即合成的。 – Joni

無論如何，2,3,5和7的倍數會被原始算法快速拒絕，所以跳過它們並不能改善p性能。算法花費大部分時間的地方在於證明具有大素數因子的數字是複合的。爲了從根本上改善性能，你應該使用更好的primality test，比如Miller-Rabin。

一個更簡單的改進是測試因子只能達到sqrt(num)，而不是num-1。如果這沒有立竿見影，請考慮一個複合數的最小素數可以有多大。另外，如果您正在尋找從1到N的素數，則使用素數篩可能更有效，或者只能通過已找到的素數檢驗可分性。

來源

2013-09-22 18:01:44 Joni

我剛剛編碼類似;-)

! Algorithm taken from https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes 
subroutine eratosthenes_sieve(n, primes) 
    implicit none 
    integer,intent(in) :: n 
    integer,allocatable,intent(out) :: primes(:) 
    integer    :: i, j, maxPrime, stat 
    logical    :: A(n) 

    maxPrime = floor(sqrt(real(n))) 
    A = .true. 

    do i=2,maxPrime 
    j = i*i 
    do 
     A(j) = .false. 
     j = j + i ; if (j .gt. n) exit 
    enddo 
    enddo !i 

    allocate(primes(count(A)-1), stat=stat) 
    if (stat /= 0) stop 'Cannot allocate memory!' 

    j = 1 
    do i=2,n ! Skip 1 
    if (.not. A(i)) cycle 
    primes(j) = i 
    j = j + 1 ; if (j > size(primes)) exit 
    enddo 
end subroutine

這個算法給你所有素數達到一定的數量，所以你可以很容易地檢查你的黃金是否包括或不包括什麼：

if (any(number == prime)) write(*,*) 'Prime found:',number

來源

2013-09-22 18:01:37

感謝您的回答。 – Andro

回答

相關問題