CareerCup

Sorry, I was trying to remember the algo from my head, and I made a couple mistakes in it. Calling it Euclid instead of Sieve for instance. Plus I iterate through the whole array while I only need to go until 1/2 way. And the arithmetic for the indices could be cleaner.

The idea behind the "Sieve" is to "cross out" each non prime up until N. The way we do this, is that each time we come across a non crossed out number, we know it is prime, and thus all multiples of this number are NOT primes, so we cross them out. By the time we reach N we will have crossed out all non prime numbers and can sum up the remaining primes. Look up the Sieve of Erathosones or something like that for a cleaner solution!

int sum_prime(int n) {
if (n <= 1)
return -1;
bool * euclid;
euclid = new bool[n-1];
for (int i = 0; i < n-1; i++) {
euclid[i] = false;
}
euclid[0] = true;
for (int i = 1; i < n-1; i++) {
if (!euclid[i]) {
int j = 2*(i+1) - 1;
while (j < n-1) {
euclid[j] = true;
j += i+1;
}
}
}
int sum = 0;
for (int i = 0; i < n-1; i++) {
if (!euclid[i])
sum += i+1;
}
return sum;
}

Can you please help to understand what is the boolean array for?
how the boolean array optimize the algorithm?

You loop through the array and "cross out" all of the non prime integers starting from low to high. Therefore if you get to a number and it hasn't been crossed out then you know that it is prime.

The interviewer than add:

You have memory to store K integer, where K is < N.

how can you improve your algorithm if you can lowest K prime number and the higest K prime number store in the array?

my guess is that the above code is already optimized using the bool array..

guys a humble request!
Even if u post pseudocode that's fine .. but please write what u r doing in ur code. it wud help people like me who don't know much coding

I agree with Smita. The whole pointe of the interview is not just coming out with the code. The interviewer will see first about your approach and then your implementation. I think it would be really nice to explain your logic in few sentences like a psuedocode and then write your own implementation would be helpful...

bool prime[N+1] = true /* initialise with true for every index */

prime[0]=false;
prime[1]=false;

for(i=2;i<=N;i++)
{
if(prime[i])
{
k=i;
for(p=2;k*p<=N;p++)
prime[k*p]=false;

}

int sum=0;

for(i=0;i<=N;i++)
if(prime[i])sum+=i;