# question query

can anybody explain me please why this code is giving TLE my code is running in O(nlog(n)) for the specified problem

http://www.codechef.com/problems/SNON08

``````#include<stdio.h>
#define MAX 10000001
#define BUF 4096

char ibuf[BUF];
int ipt = BUF;
#ifndef ONLINE_JUDGE
{
int temp;
scanf("%d",&temp);
return temp;
}
#else
while (ipt < BUF && ibuf[ipt] < '0') ipt++;
if (ipt == BUF) {
fread(ibuf, 1, BUF, stdin);
ipt = 0;
while (ipt < BUF && ibuf[ipt] < '0') ipt++;
}
int n = 0;
while (ipt < BUF && ibuf[ipt] >= '0') n = (n*10)+(ibuf[ipt++]-'0');
if (ipt == BUF) {
fread(ibuf, 1, BUF, stdin);
ipt = 0;
while (ipt < BUF && ibuf[ipt] >= '0') n = (n*10)+(ibuf[ipt++]-'0');
}
return n;
}
#endif
int prime1[MAX]={0};
void sieve(){
int i,j,count=0;
for(i=2;i<MAX;i++){

j=2;
if(!prime1[i]){
count++;
while(i*j<MAX){
prime1[i*j++]=1;
}
}
prime1[i]=count;
}
}
int main(){
sieve();
int t,n,i;
while(t--){
printf("%d\n",prime1[n]-prime1[n/2]);
}
return 0;
}
``````

You can reduce the time by checking prime’s till square root of MAX…change your for loop to for(i=2;i*i<=MAX;i++) also by skipping even numbers…

first edit your directory then check your (i=2;i<=MAX;i++)

what directory are u talking about shubham…

@hatim009 will u plzz elaborate your statement a bit little…

sorry it was a bit more

In function void sieve() change ur for() loop…to for(i=2;ii<=MAX;i++)…you can get all prime numbers iterating to square root of MAX…you can further increase the time by skipping even numbers that is change ur loop to for(i=3;ii<=MAX;i+=2)…

1 Like