PLease Help me in optimising the code


#1

vector SieveOfEratosthenes(int A)
{ vector v,v1;
bool prime[A+1];
memset(prime, true, sizeof(prime));

for (int p = 2; p * p <= A; p++)
{   
    if (prime[p] == true)
    {  
        for (int i = p * p; i <= A; i += p)
            prime[i] = false;
    }
}
for (int p = 2; p <= A; p++){
    if (prime[p]){
        v.push_back(p);
    }
}
int k=0;
for(int i=0;i<v.size();i++){
    for(int j=i;j<v.size();j++){
        if(v[i]+v[j]==A){
            v1.push_back(v[i]);
            v1.push_back(v[j]);
            k=1;
            break;
        }
    }
    if(k==1){
        break;
    }
}
return v1;

}
vector Solution::primesum(int A) {
vector c=SieveOfEratosthenes(A);
return c;

}


#2

to search for the matching primes, instead of using 2 for loops you can use lower_bound because the array of primes will always be sorted. This will make searching possible in O(nlogn) in worst case.


#3

You could rather just check if (i) and (A-i) both are primes, as you always want the sum to be A…
Also you might prefer using vector instead of bool […] as vector is space efficient.


#4
  • Using vector V is unnecessary because you have already calculated prime array and you can check that if for any i>=2 is a prime then there exists j>=2 such that prime[A-i]==true in O(1) complexity hence your nested loop is also unnecessary.

  • Your code can be modified as

      vector<int> SieveOfEratosthenes(int A)
      {
         bool prime[A+1];
         memset(prime, true, sizeof(prime));
    
      for (int p = 2; p * p <= A; p++)
    {   
    if (prime[p] == true)
      {  
          for (int i = p * p; i <= A; i += p)
          prime[i] = false;
       }
    }
    for(int i=2;i<=A;i++){
    if(prime[i] && prime[A-i]){
      return {i,A-i};
    }
     }
    return {};
    }
    
    
    vector<int> Solution::primesum(int A) {
    return SieveOfEratosthenes(A);
    
     }

#5

thanks it helps a lot