What is wrong in this code.for KPRIME..giving wrong ans in codechef and right in my system

general
, , ,
1

#include<stdio.h>
#include<string.h>
#include<math.h>
#define lim 100005

int prime[lim]={0},check[lim]={0};

int main()

{

int i,j,t,a,b,k,s;

s=(int)sqrt(lim)+1;

for(i=2;i<=s;i++)

{

if(!prime[i])

{

check[i]++;

j=2*i;

while(j<=lim)

{

prime[j]=1;

check[j]++;

j+=i;

}

}

}

scanf("%d",&t);

while(t–)

{

int c=0;

scanf("%d",&a);

scanf("%d",&b);

scanf("%d",&k);

for(i=a;i<=b;i++)

{

if(check[i]==k)

c++;

}

printf("%d\n",c);

}

return 0;

}

2

@shubham:

the mistake in ur code was that u were calculating the prime only till sqrt(lim), so the multiples of prime numbers greater than sqrt(lim) were ignored. this was the cause of WA.

Eg:

consider if the test case was :

1

87313 87313 1

since u were calculating prime only till sqrt(lim)=(316), the output should have been 1 since 87313 is a prime number but ur solution outputs 0.

link to the AC solution. :slight_smile:

1 Like
3

Got it…thanx .:slight_smile: