CodeChef submission 136795 (C++ 4.3.2) plaintext list. Status: TLE, problem SNCK04, contest SNACKDWN. By Codemutants (Codemutants), 2009-11-21 23:58:10.
//#include<iostream>
#include<string.h>
#include<stdio.h>
//#include<algorithm>
#include<string.h>
#include <stdlib.h>
#include<ctype.h>
#include<math.h>
//#include<vector>
 
bool *flag=new bool[1000000];
 
 
 
void sieve(long int L,long int U) {
long int i,j,d;
d=U-L+1; /* from range L to U, we have d=U-L+1 numbers. */
/* use flag[i] to mark whether (L+i) is a prime number or not. */
 
for (i=0;i<d;i++) flag[i]=true; /* default: mark all to be true */
for (i=(L%2!=0);i<d;i+=2) flag[i]=false;
/* sieve by prime factors staring from 3 till sqrt(U) */
for (i=3;i<=sqrt(U);i+=2) {
if (i>L && !flag[i-L]) continue;
/* choose the first number to be sieved -- >=L,
divisible by i, and not i itself! */
j=L/i*i; if (j<L) j+=i;
if (j==i) j+=i; /* if j is a prime number, have to start form next
one */
j-=L; /* change j to the index representing j */
for (;j<d;j+=i) flag[j]=false;
}
if (L<=1) flag[1-L]=false;
if (L<=2) flag[2-L]=true;
/*
for (i=0;i<d;i++) 
 
if (flag[i]) 
printf("%ld\n",L+i);
*/
//cout << (L+i) << " ";
//printf("\n");//cout << endl;
}
 
 
                 
int main()
{    
    long count =0,t;
    long n,i,j;
   //freopen("input.txt","r",stdin);
  // freopen("output.txt","w",stdout); 
    scanf("%ld",&t);
    sieve(2,1000000);
    while(t>0)
    {
              //count=0;
              scanf("%ld",&n);   
              /* 
   for (i=1; i<n;i++)
       {
       
         count+=n-i;
           }*/
           for(i=4;i<=n;i++)
                            {
                            if(flag[i]==false)
                                              count+=i/2;
                                              
                            }
           t--;
   printf("%ld\n",((n*(n-1))/2)-count);
}
 
    /*
    int n;
    scanf("%d",&n); use scanf and printf
    printf("%d",n);
    
    */
    //vector<int> v;
 
    return 0;
    
}