# Prime Generator - WA

Can you point out what’s wrong with my code?

``````#include <bits/stdc++.h>
#define ll long long
using namespace std;

void sieve(ll lowerbound, ll upperbound)
{
map<ll, bool> flag;
ll i = (lowerbound < 2 ? 2 : lowerbound);
for(; i<=upperbound; i++)
{
if(!flag[i]) // if unmarked = prime
{
flag[i] = true;
printf("%lld\n", i);
if(i*i > upperbound)
break;
// mark all multiples of i
for(ll j=i*i; j<=upperbound; j+=i)
flag[j] = true;
}
}
i++;
for(; i<=upperbound; i++)
{
if(!flag[i]){
printf("%lld\n", i);
}
}
}

int main()
{
ll t, a, b;
scanf("%lld", &t);
while(t--)
{
scanf("%lld%lld", &a, &b);
sieve(a, b);
printf("\n");
}
return 0;
}
``````

You are running loop from lowerbound if it is greater than 2 . Right? But what if it is 5-10 there is no factor of 9 in 5 to 9 except 9.So it will be a prime according to your algorithm.
The thing is you cannot even run a loop from 2 otherwise you will get a TLE.
I guess i need some time for this question.

@vishesh_345, thank you very much for pointing that out. how dumb of me.

Anyway, my first solution was to precompute the primes from 2 until 10^9 and store it in a set (https://www.codechef.com/viewsolution/14676731). But it gets TLE. So it’s not efficient given that max constraint.

I’ll think about it for much simpler & faster solution.

Have you read segmented sieve dear? It might be what you need atm. Allso, isually “true” precomputation would be, using a brute force/slow program generate all prime numbers till 10^9. Copy paste the result as an array in your actual code and then answer in O(1) time

@vijju123 you are right. I have heard this thing before segmented sieve for such types of questions but could not connect it. I will read about it. Thanks for telling.

@vijju123 segmented sieve is new to me. I will read about it later for additional knowledge. Thanks for the correction also regarding “precomputation”