sieve.gno

 1// Package sieve is an on-chain port of Go's classic concurrent prime sieve
 2// (the "prime sieve" example from the Go tour / Go source docs), implemented
 3// as a deterministic, allocation-friendly Sieve of Eratosthenes so it runs
 4// reproducibly on-chain (no goroutines, channels, or clocks) — as a reusable
 5// pure package.
 6//
 7// A live demo of this package (a gnoweb prime explorer) is at
 8// [r/moul/x/daily/sievedemo](/r/moul/x/daily/sievedemo/v0).
 9package sieve
10
11// MaxN bounds the sieve so gas stays predictable.
12const MaxN = 10000
13
14// PrimesUpTo returns every prime p with 2 <= p <= n, in ascending order,
15// using the Sieve of Eratosthenes. n is clamped to [0, MaxN]. Pure.
16func PrimesUpTo(n int) []int {
17	if n < 2 {
18		return []int{}
19	}
20	if n > MaxN {
21		n = MaxN
22	}
23
24	// composite[i] == true once i is known to be non-prime.
25	composite := make([]bool, n+1)
26	for p := 2; p*p <= n; p++ {
27		if composite[p] {
28			continue
29		}
30		for m := p * p; m <= n; m += p {
31			composite[m] = true
32		}
33	}
34
35	primes := []int{}
36	for i := 2; i <= n; i++ {
37		if !composite[i] {
38			primes = append(primes, i)
39		}
40	}
41	return primes
42}
43
44// NthPrime returns the k-th prime (1-indexed), or 0 if it lies beyond MaxN.
45// Pure helper handy for callers and tests.
46func NthPrime(k int) int {
47	if k < 1 {
48		return 0
49	}
50	primes := PrimesUpTo(MaxN)
51	if k > len(primes) {
52		return 0
53	}
54	return primes[k-1]
55}
56
57// IsPrime reports whether x is prime (trial division). Pure.
58func IsPrime(x int) bool {
59	if x < 2 {
60		return false
61	}
62	for d := 2; d*d <= x; d++ {
63		if x%d == 0 {
64			return false
65		}
66	}
67	return true
68}