Use boolean Array for Sieve

interview-questions
programming
Tags: #<Tag:0x00007f2427f3ff28> #<Tag:0x00007f2427f3fde8>

#1
vector<int> Solution::primesum(int A) {
    int xx=A+1;
    vector<bool>v(xx,1);
    v[0]=0;
    v[1]=0;
    vector<int>res(2);
    int i,j,k=v.size();
    int size = sqrt(k);
    for(i=2;i<=size;i++){
        if(v[i]){
            for(j=2;j*i<=k;j++){
                v[i*j]=0;
            }
        }
    }
    for(i=2;i<=A;i++){
        if(v[A-i]==1 && v[i]==1){
            res[0]=i;
            res[1]=A-i;
            //cout<<i<<" "<<A-i<<endl;
            return res;
        }
    }
}

#2

It didn’t work out for python :frowning:


#3

don’t go for : sieve of eratosthenes , time is not an issue here but memory is !