Here’s a very simple algorithm that generates a list of all random numbers up to “n.” You just pass it an bool array of size “n+1” and “n” itself. The algorithm marks elements with prime indices in the array as true, and sets the rest to false.

void euler_sieve(int n, bool *a) {
// Initialize the array
a[0] = false;
a[1] = false;
for (int i = 2; i <= n; i++) {
a[i] = true;
}
for (int i = 2; i <= n/2; i++) {
/* If the current elements is prime,
* mark all its multiples as not prime
*/
if (a[i]) {
for (int j = i + i; j <= n; j += i) {
a[j] = false;
}
}
}
}

### Like this:

Like Loading...