bench_prime_sieve/
lib.rs

1//! Sieve of Eratosthenes benchmark — counts primes up to N.
2
3#![cfg_attr(target_os = "none", no_std)]
4
5use subsoil as _;
6
7const N: usize = 100_000;
8
9/// Sieve of Eratosthenes: count primes up to N.
10/// Returns the prime count (π(100000) = 9592).
11pub fn prime_sieve() -> u32 {
12    // Use static mut to avoid 100KB stack allocation — PVM stack is limited.
13    // Initialized to 1 (prime) — reset to 0 for composites during sieve.
14    static mut IS_PRIME: [u8; N] = [1; N];
15
16    #[allow(static_mut_refs)]
17    let is_prime = unsafe { &mut IS_PRIME };
18    // Re-initialize each call (static persists across calls in the same instance)
19    let mut i: usize = 0;
20    while i < N {
21        is_prime[i] = 1;
22        i += 1;
23    }
24    is_prime[0] = 0;
25    if N > 1 {
26        is_prime[1] = 0;
27    }
28
29    // Sieve: mark multiples of each prime starting from p*p
30    let mut p: usize = 2;
31    while p * p < N {
32        if is_prime[p] != 0 {
33            let mut j = p * p;
34            while j < N {
35                is_prime[j] = 0;
36                j += p;
37            }
38        }
39        p += 1;
40    }
41
42    // Count primes
43    let mut count: u32 = 0;
44    let mut i: usize = 0;
45    while i < N {
46        count += is_prime[i] as u32;
47        i += 1;
48    }
49    count
50}
bench_prime_sieve/lib.rs

bench_prime_sieve/
lib.rs
