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);
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: https://www.codechef.com/problems/BSP1
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,

Please Like :slightly_smiling_face:

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").