### GreedyXploit's blog

By GreedyXploit, history, 7 weeks ago,

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


• -3

 » 7 weeks ago, # |   0 Auto comment: topic has been updated by GreedyXploit (previous revision, new revision, compare).
 » 7 weeks ago, # |   0 Just make sure it doesn't go out of bounds on the primes vector. Codefor(long long i = 0; i