!------------------------------ooO0Ooo------------------------------
!
!   Sieve of Erstothenes
!   written to compare speed of Fortran vs Python
!   	Ian Robinson
!			www.starfishprime.co.uk
!------------------------------ooO0Ooo------------------------------

program Sieve_of_Eratasthenes

    implicit none
    integer:: N, startPos, sqrStartPos, i, j, midpoint, rootN, n_primes
    real :: startTime, stopTime
    Parameter (N = 1000000000)
    Logical, dimension(2:N) :: Primes
    
    call cpu_time(startTime)
    
    midPoint = int (N/2)
    rootN= int(sqrt(real(N)))
    
  ! Initialise the array elements to true ..
    do  i= 2, N
        Primes(i) = .True.
    end do
    
    !print *, "The Sieving Begins"
    startPos=2
    do	
        j=0
        sqrStartPos =startPos**2
        do
            i=sqrStartPos + (j*startPos)
            if (i>N) exit
	    Primes(i) = .False.
	    j=j+1
	end do

	do
	    startPos=startPos+1
	    if (Primes(startPos) .eqv. .True.) exit
	end do
	
	if (startPos > rootN) exit
     end do
     
    call cpu_time(stopTime)
    print *, 'Elapsed time, s : ',  (stopTime - startTime)
  

!    do i=N,(N-100), -1
!    if(primes(i) .eqv. .True.) Print "(3i10)", i
!    end do



    
    n_primes=0
    do i=2,N
	if(Primes(i) .eqv. .True.) n_primes=n_primes+1
    end do
    
    print *, "Number of primes 2-", N, "  = ", n_primes
!	print *, "Primes Determined - beginning data-write"
!	open(1, file = 'primes.dat', status = 'old')  
!    do i=1,N
!		if(primes(i) .eqv. .True.) write (1,"(I12)") i
!    end do
!    close(1)
!    open(1, file = 'primes.dat', status = 'old')  
!    do i=1,N
!		if(primes(i) .eqv. .True.) write (1,*) i
!    end do
!    close(1)
    !print *, "Data-write completed"
    

end program Sieve_of_Eratasthenes
