sieve method

help
1

problem link:-https://www.codechef.com/problems/ALGPRX/
#include
#include<stdio.h>
#include<math.h>
using namespace std;
void sieve();
#define r 1000000
bool prime[r];
int main()
{
int t,n,s,dif,k,a,b,i,j;
sieve();
scanf("%d",&t);
while(t–)
{
s=0;
cin>>a;
for(i=2;i<a;i++)
{
if(prime[i]==true)
s+=i;
}
printf("%d\n",s);
}
}

void sieve()
{
int i,j;
for(i=0;i<r;i++)
prime[i]=true;
prime[0]=false;
prime[1]=false;
for(i=2;i*i<r;i++)
{
if(prime[i]==true)
{
for(j=i*i;j<r;j+=i)
prime[j]=false;
}
}
}
2

Try declaring I and j in sieve as long long int. Because when we need to solve for numbers >10^5, j=I*I makes cross 10^10, causing overflow.

This gives a runtime error during execution.

Or you are facing some other issues?

3

Your code will get TLE, better optimize it.
And why are you seiving again and again, doing it once upto MAX value, isn’t that better?
It is my implementation (got AC in 0.00 sec) have a look.

2 Likes
4

His code will get TLE and moreover we don’t really need to run the outer loop upto 1000000, running outer loop upto 1000 is sufficient

1 Like
5

Wait, isn’t sieve being called out of loop? I thought its being called once :/. Can you please clarify here? :slight_smile:

1 Like
6

If you call sieve only once it’ll cause TLE, the second function optimises the sum by saving prefix sums upto i.
Sieveing is actually used to save all the prime numbers needed upto MAX, so we call sieve only once, calling it again and again will have higher time complexity and it’ll cause TLE, so normally sieve is called only once out of the for loop.

1 Like
7

I think is a very good problem for those learning sieve and precomputations. If you only use sieve then you will get TLE. Apart from sieve you will also have have to precompute the sum upto given upper bound . After that you will get your answer in O(1) for each query.

Time complexity analysis without precomputation:-

sieve- O(nlog(logn)),for each query you will have to run O(m), so if there are t queries then its complexity becomes O(nlog(logn))+O™ where tm<=nn --> O(nn)

Time complexity analysis with precomputation:-

sieve:- O(log(log(n)), for precomputing sum upto upper bound O(n). For each query answer is in O(1), so there can be atmost n queries(see it via given given constraints) so it is O(n).
Overall complexity:- O(nlog(log(n))+O(n)+O(n)—>O(nlog(logn)).

P.S.:- I got my AC in 5th try. LINK
You can comment here if you have any doubts in my solution. @vijju123 @adhish_kapoor

If you feel that I have answered your question, mark it as accepted.

2 Likes
8

Thanks dear. I will give it a shot and get back to you sometime after my mid-sems :slight_smile:

9

I can understand.

Academic pressure.