Tin

Examples · 11 of 339

11-sieve

Arrays and tight loops: the sieve of Eratosthenes.

examples/11-sieve.tintin 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