Deepak and Primes II

#1

what’s wrong with my code ?

#include<bits/stdc++.h>
#define N 100004
#define ll long long
using namespace std;
bitset<N> arr;
bitset<N> pp;
void sieves(){
	for(long  i = 3 ;i<N;i+=2){
		arr[i] = 1;
		}
		arr[2] = true;
		for(long i = 3 ;i<N;i+=2){
			if(arr[i]){
				for(long j = i*i ; j < N ; j += 2*i){
    					arr[j] = 0;
				}
			}
		}
		
}

void SegmentedSieve(ll a, ll b){
    pp.set();
	if(a==2){
		cout<<"2\n";
		a = 3;
	}
	if(a&1==0){
		a++;
		pp[0] = 0;
	}

    for(ll i = 3; i*i<= b; i+=2){
        for(ll j = a ; j <= b ;j+=2){ // a is always odd we  iterate
            if(arr[i]){     // only start from a (odd)with the step of 2
                if(j==i)
                    continue;
                else if(j%i == 0)
                    pp[j-a] = 0;
            }
        }
        
    }
    for(ll i = a;i<=b;i+=2){ // a is odd iterate only odd
        if(pp[i-a]){
            cout<<i<<endl;
        }
    }
    cout<<endl;
}
int main() {
	sieves();

    ll x, y;
    int t;
    cin>>t;
    while(t--){
    cin>>x>>y;
    SegmentedSieve(x, y);
    }
	return 0;
}
#2

Input

2
2 10
200000 200100

Your Output

2
3
5
7

200006
200038
200048
200084
200086
200092
200098

Expected Output

2
3
5
7

200003
200009
200017
200023
200029
200033
200041
200063
200087
#3

TESTCASE # 1 : timelimit (Time: 5.97 s)
TESTCASE # 2 : wrong-answer (Time: 0.11 s)
TESTCASE # 3 : correct (Time: 0.26 s)
TESTCASE # 4 : correct (Time: 0 s)
TESTCASE # 5 : correct (Time: 0.16 s)
TESTCASE # 6 : timelimit (Time: 5.96 s)
TESTCASE # 7 : wrong-answer (Time: 0.1)


for(ll i = 3; i*i<= b; i+=2){
        for(ll j = a ; j <= b ;j+=2){ // a is always odd we  iterate
            if(arr[i]){     // only start from a (odd)with the step of 2
                if(j==i)
                    continue;
                else if(j%i == 0)
                    pp[j-a] = 0;
            }
        }
        
    }

can we use the fect that even number can not be prime
why my solution not working

#4

Yeah but your code is still outputting even numbers. Maybe your offset is Wrong.
Debug this testcase on your code.

#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#6

bhiya i am not getting this quetion plz can you tell where is bug.

TESTCASE # 1 : timelimit (Time: 5.97 s)
TESTCASE # 2 : wrong-answer (Time: 0.08 s)
TESTCASE # 3 : correct (Time: 0.17 s)
TESTCASE # 4 : correct (Time: 0 s)
TESTCASE # 5 : correct (Time: 0.11 s)
TESTCASE # 6 : wrong-answer (Time: 4.56 s)
TESTCASE # 7 : wrong-answer (Time: 0.09 s)
#7

bhiya i am not getting this quetion plz can you tell where is bug.

it still not working on hidden test cases.

#8

Check this out! Tried to correct your code. Came up with this.

#include<bits/stdc++.h>
#define ll long long int
#define N 100005
using namespace std;
bitset<N> arr;
bitset<N> pp;

void sieve(int n, vector<ll> &p) {
    arr.set(); arr[0] = arr[1] = 0;
    for(ll i = 0; i <= n; i += 1){
        if(arr[i]) {
            p.push_back(i);
            for(ll j = 2 ; j * i <= n ; j += 1)
                    arr[j * i] = 0;
        }
	}
}

void SegmentedSieve(ll a, ll b) {
    // find all primes till square root of b
    vector<ll> primes;
    sieve(ceil(sqrt(b)), primes);
    pp.set();
    for(auto prime : primes) {
        ll start = ceil(double(a) / prime);
        start = ((start <= 1) ? 2 : start);
        for(ll j = start; j * prime <= b; j += 1)
            pp[j * prime - a] = 0;
    }
    for(ll i = a; i <= b; i++)
        if(pp[i - a])
            cout << i << " ";
    cout << endl;
}
int main() {
    int t;
    ll x, y;
    cin >> t;
    while(t--) {
        cin >> x >> y;
        SegmentedSieve(x, y);
    }
	return 0;
}
1 Like