gno.land/p/moul/x/daily/sieve/v0⧉

1// Package sieve is an on-chain port of Go's classic concurrent prime sieve2// (the "prime sieve" example from the Go tour / Go source docs), implemented3// as a deterministic, allocation-friendly Sieve of Eratosthenes so it runs4// reproducibly on-chain (no goroutines, channels, or clocks) — as a reusable5// pure package.6//7// A live demo of this package (a gnoweb prime explorer) is at8// [r/moul/x/daily/sievedemo](/r/moul/x/daily/sievedemo/v0).9package sieve1011// MaxN bounds the sieve so gas stays predictable.12const MaxN = 100001314// 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 = MaxN22	}2324	// 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			continue29		}30		for m := p * p; m <= n; m += p {31			composite[m] = true32		}33	}3435	primes := []int{}36	for i := 2; i <= n; i++ {37		if !composite[i] {38			primes = append(primes, i)39		}40	}41	return primes42}4344// 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 049	}50	primes := PrimesUpTo(MaxN)51	if k > len(primes) {52		return 053	}54	return primes[k-1]55}5657// IsPrime reports whether x is prime (trial division). Pure.58func IsPrime(x int) bool {59	if x < 2 {60		return false61	}62	for d := 2; d*d <= x; d++ {63		if x%d == 0 {64			return false65		}66	}67	return true68}69