C the sum of primes

Question

The challenge is to calculate the sum of the first 1000 primes. The code applies a sieve thanks to past answer, here, and works but I wonder about the flexibility of this solution.

#include <stdio.h>
unsigned long compute_sum_of_primes(int primes_needed) {
 int sieve_size = 20 * primes_needed;
 int sieve[sieve_size];
 unsigned long sum = 0;
 for (int i = 0; i < sieve_size; i++) {
 sieve[i] = 1;
 }
 for (int prime = 2; primes_needed > 0; prime++) {
 if (sieve[prime]) {
 sum += prime;
 primes_needed--;
 for (int composite = prime + prime; composite < sieve_size; composite += prime) {
 sieve[composite] = 0;
 }
 }
 }
 return sum;
}
int main() {
 unsigned long sum_of_primes = compute_sum_of_primes(1000);
 printf("%lu\n", sum_of_primes);
}

Answer 1

A simpler way to initialize the sieve variable-sized array is using memset (from #include <string.h>):

memset(sieve, 1, sizeof(sieve));

However, although this works, know that it doesn't set the values to 1, but actually to 0x01010101 =わ 16843009, because memset sets bytes, regardless of the actual type of the underlying array.

In your case this is fine, because you need effectively a boolean array, so as long as the values are nonzero, it doesn't make a difference that they are not actually 1 but 16843009.

However, readers might look suspiciously at the program. A comment explaining that the values are 16843009 may help, but a better way is to change the type of the array to char. This way the array values will be really 1. But much more importantly, you will significantly reduce the memory footprint, to 25% of the original.

---

The number 20 here looks like pure magic:

int sieve_size = 20 * primes_needed;

At the minimum, it would be good to add a comment explaining this choice, and its implications in case of small and large values of n.

• Legato: I actually did that before, but I get a variable-sized object may not be initialized error not sure how it needs to be structured to work as you describe. On the topic of the sieve variable...it's magic. I ran some tests looking for nth primes and noticed most occurred within a factor of 10 and a bit so doubling that to twenty is meant to encompass that, it works until the 100,000,000th prime which is 2,038,074,743 and goes over. Not sure if there's an actual standard for this and communicating/amending this weird structure is why I seek the CR's guidance.
• janos: You're right, a variable-sized array cannot be initialized this way :( I rewrote with an alternative using memset.
• janos: @JS1 you're absolutely right, thanks for pointing out, updated the post