Help me in Segmented Sieve | Why it gives error for small and long ranges

Revision en2, by GreedyXploit, 2020-11-30 19:27:31

I am learning Segmented Sieve but i don't know why my program freezes when i give input to find primes between 1 to 10

here is my code pls say what is my error and how do i solve it

#include<iostream>
#include<cmath>
#include<vector>
#include<algorithm>

using namespace std;

vector<long long> SimpleSieve(long long rsqrt)
{
	vector<long long> primes;
	bool isprime[rsqrt+1];
	for(long long  i = 0 ; i<=rsqrt ; i++)
		isprime[i] = true;

	for(long long i = 2 ; i<=rsqrt ; i++)
	{
		if(isprime[i])
		{
			primes.push_back(i);
			for(long long j = i*i ; j<=rsqrt ; j+=i)
				isprime[j] = false;
		}
	}
	return primes;
	
}

int main()
{
	long long  l , r;
	cin>>l>>r;
	long long rsqrt = sqrt(r);
	vector<long long>primes = SimpleSieve(rsqrt);

	bool is_prime[r-l+1];
	for(long long  i =0 ; i<=r-l ; i++)
	{
		is_prime[i] = true;
	}	

	for(long long  i = 0 ;primes[i]*primes[i]<=r ; i++)
	{
		long long base = (l/primes[i])*(primes[i]);
		if(base<l)
			base = base + primes[i];
		
		for(long long j = base ; j<=r ; j+=primes[i])
		{
			is_prime[j-l] = false;
	
		}	
		if(base == primes[i])
			is_prime[base - l] = true;
	}
	
	for(long long i = 0 ; i<=r-l; i++)
	{
		if(is_prime[i] == true)
			cout<<i+l<<"\n";
	}
}
Tags segmented sieve, #help error, #help me

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English GreedyXploit 2020-11-30 19:27:31 45
en1 English GreedyXploit 2020-11-30 18:39:27 1352 Initial revision (published)