module mdl contains function mul_mod(a,b,m)result(ret) implicit none integer(8),value::a,b,m integer(8)::ret,tmp a=mod(a,m) b=mod(b,m) ret=0 do while(b>1) if(mod(b,2)==0)then tmp=a if(tmp>=m-a)tmp=tmp-m a=mod(a+tmp,m) b=b/2 else if(ret>=m-a)ret=ret-m ret=mod(ret+a,m) b=b-1 end if end do if(ret>=m-a)ret=ret-m ret=mod(ret+a,m) end function integer(8) function pow(a,n,p) implicit none integer(8),value::a,n,p a=mod(a,p) pow=1 do while(n>0) if(mod(n,2)==1)pow=mul_mod(pow,a,p) n=n/2 a=mul_mod(a,a,p) end do end function logical function isPrime(a) integer(8)::p(16)=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53],q,i,j,k,x,y,tmp integer(8),value::a logical::flag isPrime=.true. if(a==2)return if(a==1.or.mod(a,2)==0)then isPrime=.false. return end if q=a-1 do while(mod(q,2)==0) q=q/2 end do do i=1,size(p) x=pow(p(i),q,a) y=q do while(y/=a-1.and.x/=1.and.x/=a-1) y=y*2 x=mul_mod(x,x,a) end do if(x/=a-1.and.mod(y,2)==0)then isPrime=.false. return end if end do end function end module program main use mdl implicit none integer::n integer(8)::i,j,k integer(8),allocatable::x(:) read*,n allocate(x(n)) do i=1,n read*,x(i) if(isPrime(x(i)))then print*,x(i),1 else print*,x(i),0 end if end do end program