# Time limit exceeded in my program help me to fix it

#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);
while(t–)
{
scanf("%ld",&n);
sum=0;
for (int i = 0; i <=j ; ++i)
{
if (num[i]>n)
{
break;
}
else
sum+=num[i];
}
// printf("%ld\n",sum);
}
for (int i = 0; i < f; ++i)
{
/
code */
}
return 0;
}

Atleast provide the question so that one can help

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.

https://www.codechef.com/problems/BSP1 this is the problem link

Hey @n_ve_n_612
This is my solution

I calculated the primes by checking only till their square root,