#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<ctype.h>
#include<math.h>
long int num[100000],j=0;
long int prime_check(long int a)
{
long int flag=1;
if(a==1)
return 0;
for ( int i = 2; i <= a/2; ++i)
{
if (a%i==0)
{
flag=0;
break;
}
}
return flag;
}
int main(int argc, char const argv[])
{
long int t,sum=0,n;
num[0]=2;
j=1;
for (long int i = 3; i <=1000000; ++i)
{
if(prime_check(i))
{
num[j++]=i;
}
}
scanf("%ld",&t);
long int jadu[t],f=0;
while(t–)
{
scanf("%ld",&n);
sum=0;
for (int i = 0; i <=j ; ++i)
{
if (num[i]>n)
{
break;
}
else
sum+=num[i];
}
jadu[f++]=sum;
// printf("%ld\n",sum);
}
for (int i = 0; i < f; ++i)
{
printf("%ld\n",jadu[i]);
/ code */
}
return 0;
}
First provide the problem link…
Atleast provide the question so that one can help
Problem link: BSP1 Problem - CodeChef
Your code is too slow. You need to precompute all primes till 1e6 by sieving. You can store the prefix sum till each prime. Then use binary search to find the index of the greatest prime that is less than or equal to n. You should print the prefix sum of that index.
will linear search wont work?
Due to the given constraints, no. It won’t.
Hey @n_ve_n_612
This is my solution
I calculated the primes by checking only till their square root,
Please Like 
Your code shouldn’t pass. O(n \sqrt{n}) is slow for n =10^6 and T = 10^3. The test cases were weak (there’s no explicit statement like "the sum of all n does not exceed 10^6").