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 readInt()
        {
            int temp;
            scanf("%d",&temp);
            return temp;
        }
#else
int readInt() {
 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;    
  t=readInt();
  while(t--){
   n=readInt();
   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