problem 007

ガウスの素数定理によって大体の値の見当をつけてそこまでの素数をやや大目に求めます。

ソース・プログラム

    program PEuler007
      implicit none
      integer, parameter :: np = 10001
      integer, allocatable :: iptab(:)
      integer :: n 
      ! np ~ n / log(n) ! approximate number of primes less than n : Gauss   
      ! approximate np-th prime n ~ np * log(n) ~ np * log( np * log(n) ) ...  
      n = np * log( np * log( real(np) ) ) + 3 
      iptab = ieratos(n)
      print *, iptab(np)
      stop
    contains  
      function ieratos(n) ! thieve of Eratostenes
        integer, intent(in) :: n
        integer, allocatable :: ieratos(:)
        logical :: tab(n)
        integer :: i
        tab = .true.
        tab(1) = .false.
        do i = 2, int( sqrt(real(n)) ) 
          if ( tab(i) ) tab(i * i:n:i) = .false.
        end do
        ieratos = pack( [ (i, i = 1, n) ], mask = tab )
        return
      end function ieratos
    end program PEuler007

実行結果

104743
続行するには何かキーを押してください . . .