PROGRAM Prime
! Find Prime  
! single processor
 IMPLICIT none
 INTEGER :: long
 PARAMETER (long = SELECTED_INT_KIND(10))
 INTEGER(long), PARAMETER :: n=1000000
 INTEGER(long), ALLOCATABLE :: p(:), x(:)
 INTEGER, INTRINSIC :: MOD, FLOOR, SIZE
 REAL, INTRINSIC :: SQRT

 INTEGER(long) :: i,j,s,xs,ps,m,ms
 INTEGER :: hz, clock0, clock1
 real :: time
 INTEGER, ALLOCATABLE :: t(:)


 ALLOCATE (t(1))
 CALL SYSTEM_CLOCK(count_rate=hz)
 CALL SYSTEM_CLOCK(count=clock0)
 

 m=floor(sqrt(n*1.0))
 s=floor((m-3.0)/2.0)+1
 ALLOCATE (p(s))
 ps=size(p)
 p=(/ (i, i=3, m, 2) /)
 ms=p(ps)
 s=floor((n-ms-2.0)/2.0)+1
 ALLOCATE (x(s))
 x=(/ (i,i=ms+2, n, 2) /)
 i=1
 xs=size(x)
 DO 
   IF (p(i) .NE. 0) THEN
     WHERE (MOD(p(i+1:ps),p(i)) .EQ. 0) p(i+1:ps)=0
     WHERE (MOD(x(1:xs),p(i)) .EQ. 0) x(1:xs)=0
   END IF
   i = i+1
   IF (i == ps) EXIT
 END DO


 CALL SYSTEM_CLOCK(count=clock1)
 t = clock1-clock0
 time = real(sum(t))/(real(hz)*size(t))
 PRINT *, 'time : ',time
 
 PRINT *, 'n : ',n
! PRINT *, PACK(p,MASK=p>0)
! PRINT *, PACK(x,MASK=x>0)
! PRINT *, 'no of prime: ', COUNT(p>0)
 PRINT *, 'no of prime: ', COUNT(x>0)+COUNT(p>0)+1
 ! + 1 is for the number 2

END PROGRAM Prime