I'm trying to learn Zig using the website https://exercism.org/. I was solving this exercise, which requires us to find the nth prime number.
My idea was to generate all of them during comptime
and return as required; this is my current my code:
const std = @import("std");
const mem = std.mem;
const buffer_size = 100000;
fn sieve(comptime buffer: []usize, comptime limit: usize) []usize {
if (limit < 2)
return buffer[0..0];
const sqrt_limit = std.math.sqrt(limit);
var bitset = std.StaticBitSet(limit + 1).initFull();
var n: usize = 3;
var i: usize = 1;
buffer[0] = 2;
while(n <= sqrt_limit): (n += 2) {
if (!bitset.isSet(n))
continue;
buffer[i] = n;
i += 1;
var j = 2 * n;
while (j <= limit): (j += i) {
bitset.unset(j);
}
}
while (n <= limit) : (n += 2) {
if (!bitset.isSet(i))
continue;
buffer[i] = n;
i += 1;
}
return buffer[0..i];
}
var primes_buffer: [buffer_size]usize = undefined;
const primes = sieve(&primes_buffer, buffer_size);
pub fn prime(allocator: mem.Allocator, number: usize) !usize {
_ = allocator;
return primes[number-1];
}
But when I try to compile this, I'm getting the following error:
nth_prime.zig:15:15: error: unable to evaluate comptime expression
nth_prime.zig:15:11: note: operation is runtime due to this operand
nth_prime.zig:39:21: note: called from here
Why am I not able to populate my array at comptime
, and why is this line problematic?
buffer[0] = 2;
I think its because the buffer primes_buffer
is actually a runtime value, so you can't get it to work in that way. One way to write it would be like:
const primes = blk: {
const buffer_size = 1000;
@setEvalBranchQuota(buffer_size * buffer_size);
var primes_buffer: [buffer_size]usize = undefined;
const len = sieve(&primes_buffer, buffer_size);
break :blk .{ primes_buffer, len };
};
fn sieve(comptime buffer: []usize, comptime limit: usize) usize {
if (limit < 2)
return buffer[0..0];
const sqrt_limit = std.math.sqrt(limit);
var bitset = std.StaticBitSet(limit + 1).initFull();
var n: usize = 3;
var i: usize = 1;
buffer[0] = 2;
while (n <= sqrt_limit) : (n += 2) {
if (!bitset.isSet(n))
continue;
buffer[i] = n;
i += 1;
var j = 2 * n;
while (j <= limit) : (j += n) { // should increment j by n
bitset.unset(j);
}
}
while (n <= limit) : (n += 2) {
if (!bitset.isSet(i))
continue;
buffer[i] = n;
i += 1;
}
return i;
}
pub fn prime(allocator: mem.Allocator, number: usize) !usize {
_ = allocator;
if (number >= primes[1]) {
@panic("no"); // or return an error
}
return primes[0][number];
}
This way, the scope we defined as blk
will run and evaluate in comptime.