guys i am trying for three days to solve this problem.i had used the sieve of eratosthenes algorithm but still can't beat the time limit.is there any other faster algorithm to solve the problem.plz help
Feb '11
Dec '17
plz elaborate a little more.does sieve of eratosthenes algo can beat the time in case if it is not implemented properly.
below is the code
code accepted
OK, for starters do not use cout-cin. Printf-scanf are much faster. Try that and post whether you still have TLE or not. And it is actually a sticky topic here in C/C++ forum.. why you haven't read it?
i used scanf,printf still its coming TLE.what to do now?
if you had done the problem plz see if my algo is alright.
Skimmed your code and it doesn't look like sieve. You don't test on primality during sieving. You just sieve and what's left are primes. And because of that you're doing the same work over and over again => TLE. Find primes once (up to sqrt(10**9)) anyhow you like and then sieve requested intervals. Each new interval is kind of segment in which you're interested.
didnt get you.ok we will look at a simple case lets see the range is upto 10000.as you said i had found the primes up to100.now we have to found the primes from 1000 to 5000 how to do that?
Right direction. Just sieve [1000..5000] with what you already got. Each already found prime removing its divisors. And you need actually not up to 10^4, but up to sqrt(10^9). It seems you need to go back a bit and rethink sieving. After that apply the same "pattern" on requested intervals.
you are not getting me see if we have to found the prime between 1000 to 5000.then as you are saying we have to check if 1000 is multiple of any one of the list of primes we got then 1001 then 1002 and so on .I think its bit tedious.let me explain a little bit
for finding primes between 1 to n its ok but within a range lets say m to n we have to check for m whether its multiple of any one of the primes then remove its multiple then for m+1 an so on.how else we can remove the composites
You shouldn't check anything! Just sieve the interval, make prime[i] = False (i from [0..n-m]) with primes you already have, primes you calculated just once. Each prime deletes its divisors in the interval..
thanks gorlum
I worked it out your way and the solution got accepted and timing is 5.4.As people are getting it in 0-1 seconds what are the other ways
#include <bits/stdc++.h>
using namespace std;
#define ll long long
vector v;
int sieve_of_erathosis(ll m)
{
bool mark[m];
memset(mark,true,sizeof(mark));
for(ll i=2;i<m;i++)
{
if(mark[i]==true)
{
v.push_back(i);
for(ll j=i*2;j<m;j=j+i)
mark[j]=false;
}
}
return 0;
}
int segmented_sieve(ll n,ll right)
{
ll m=floor(sqrt(n))+1;
ll low=m;
ll high=m*2;
while(low<n)
{
bool mark[m+2];
memset(mark,true,sizeof(mark));
for(ll i=0;i<v.size()&&v[i]<floor(sqrt(n))+1;i++)
{
ll lolimit=floor(low/v[i]) * v[i];
if(lolimit<v[i])
lolimit+=v[i];
for(ll j=lolimit;j<high;j+=v[i])
mark[j-low]=false;
}
for(ll j=low;j<high;j++)
if(mark[j-low]==true)
if(j>=right&&j>v[v.size()-1])
printf("%lld\n",j);
low=low+m;
high=high+m;
if(high>n)
high=n;
}
return 0;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll no;
ll m;
m=100001;
sieve_of_erathosis(m);
scanf("%lld",&no);
while(no–)
{
ll right,n;
scanf("%lld%lld",&right,&n);
for(ll i=0;i<v.size();i++)
{
if(v[i]>=right&&v[i]<=n)
printf("%lld\n",v[i]);
}
if(n>=v[v.size()-1])
segmented_sieve(n,right);
}
return 0;
}
what wrong with this code?
| Topic | Category | Replies | Views | Activity |
|---|---|---|---|---|
| SPTTRN1 - Straight Line Spiral Pattern (Act 1) | C and C++ | 0 | 37 | 28d |
