Prime1:spoj

general
, , ,
1

My code is giving false value and is giving false values.

  #include<stdio.h>
  #include<stdlib.h>
  int main()
  {
int t,*prime;
long long int m,n,i,j;
scanf("%d",&t);
for(i=0;i<t;i++)
{
scanf("%lld%lld",&m,&n);
prime=(int*)(malloc((n*m)*sizeof(int)));

for(i=m;i<=n;i++)
 {
  prime[i]=1;
 }
prime[0]=0;
prime[1]=0;
for(i=m;i<=n;i++)
   {
   if(prime[i]!=0){
        for(j=2;j*i<=n;j++)
        {
        prime[j*i]=0;
        }
   }
   }
 for(i=m;i<=n;i++)
 {
     printf("%lld\n",i);
 }
free(prime);
m=0;n=0;
}

return 0;
}

2

Your implementation of sieve is not correct. Refer here for the very basic and correct implementation of sieve.

Also, The range is large, this will not work. Allocation of such large memory is not allowed. Refer this and this.

1 Like