Prime Generator - WA

general
1

Problem: Link

Submission: Link

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;
}
2

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.

3

@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.

4

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

5

@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.:slight_smile:

6

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