2

質問が重複していないことを願っていますが、提案されたトピックでは同様の問題は発生しませんでした。数値が素数かどうかをチェックする関数があります。現在、これは素数を検索する最も遅い方法です。

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 番目のバージョンでは、2、3、5、7 で割り切れるすべての数など、半分以上の数が除外されています。Linux の「time」プログラムで実行の時間を計測すると、「改善された」バージョンの実行速度が同じように遅くなる可能性はありますか? 明らかなトリックがありませんか？

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

2 に答える 2

7

いずれにせよ、2、3、5、7 の倍数は元のアルゴリズムによってすぐに拒否されるため、それらを飛び越えてもパフォーマンスはまったく向上しません。アルゴリズムがほとんどの時間を費やすのは、大きな素因数を持つ数が合成であることを証明することです。パフォーマンスを根本的に改善するには、Miller-Rabin などのより優れた素数性テストを使用する必要があります。

sqrt(num)より単純な改善は、 ではなくまでの因子のみをテストすることnum-1です。それがすぐに意味をなさない場合は、合成数の最小の素因数がどれくらい大きくなるかを考えてみてください。また、1 から N までの素数を探している場合は、素数ふるいを使用するか、既に見つかった素数だけで割り切れるかどうかをテストする方が効率的かもしれません。

于 2013-09-22T18:01:44.860 に答える
2

最近、似たようなコードを書いたばかりです ;-)

! 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-22T18:01:37.493 に答える