Examples · 11 of 339
11-sieve
Arrays and tight loops: the sieve of Eratosthenes.
tin run examples/11-sieve.tin// Arrays and tight loops: the sieve of Eratosthenes.
fn primesBelow(limit: int): int[] {
var composite: bool[] = []
for i in 0..limit { composite.push(false) }
var primes: int[] = []
for n in 2..limit {
if composite[n] { continue }
primes.push(n)
// int is 32-bit and wraps on overflow, so only square n when it fits
if n > limit / n { continue }
var multiple = n * n
while multiple < limit {
composite[multiple] = true
multiple += n
}
}
primes
}
fn main() {
let small = primesBelow(60)
print(small)
let many = primesBelow(2000000)
print("{many.len} primes below two million")
print("the largest is {many[many.len - 1]}")
} [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59]
148933 primes below two million
the largest is 1999993