Calculating primes
(1381 words)Creating a list of primes takes a long time. This is especially true if you are using the very boring and simple sieve algorithm. In Zig, this is really easy to do:
pub fn calculate_prime_numbers (comptime size: usize) std.StaticBitSet(size) {
var sieve = std.StaticBitSet(size).initFull();
sieve.setValue (0, false);
sieve.setValue (1, false);
const last: usize = @intFromFloat(@sqrt(@as(f64, @floatFromInt(size))));
for (2..size) |n| {
if (sieve.isSet(n)) {
results.set(n);
}
var i: usize = n * 2;
while (i <= last) : (i += n) {
sieve.setValue(i, false);
}
}
return results;
}
The code is really simple. It creates a sieve set, initially full, except for the number 0 and 1. It then looks through from the number 2 up to the square root of the size parameter given, and then looks at the sieve set to see if the bit is set. If it is, then it goes from double the current number up to the size parameter jumping by the current number, and clears the sieve bits, effectively removing all the multiples of the current number as not prime for future iterations.
more...