sieve.gno
3.99 Kb · 180 lines
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).
5package sieve
6
7import (
8 "strconv"
9 "strings"
10)
11
12// MaxN bounds the sieve so gas stays predictable.
13const MaxN = 10000
14
15// PrimesUpTo returns every prime p with 2 <= p <= n, in ascending order,
16// using the Sieve of Eratosthenes. n is clamped to [0, MaxN]. Pure.
17func PrimesUpTo(n int) []int {
18 if n < 2 {
19 return []int{}
20 }
21 if n > MaxN {
22 n = MaxN
23 }
24
25 // composite[i] == true once i is known to be non-prime.
26 composite := make([]bool, n+1)
27 for p := 2; p*p <= n; p++ {
28 if composite[p] {
29 continue
30 }
31 for m := p * p; m <= n; m += p {
32 composite[m] = true
33 }
34 }
35
36 primes := []int{}
37 for i := 2; i <= n; i++ {
38 if !composite[i] {
39 primes = append(primes, i)
40 }
41 }
42 return primes
43}
44
45// NthPrime returns the k-th prime (1-indexed), or 0 if it lies beyond MaxN.
46// Pure helper handy for callers and tests.
47func NthPrime(k int) int {
48 if k < 1 {
49 return 0
50 }
51 primes := PrimesUpTo(MaxN)
52 if k > len(primes) {
53 return 0
54 }
55 return primes[k-1]
56}
57
58// IsPrime reports whether x is prime (trial division). Pure.
59func IsPrime(x int) bool {
60 if x < 2 {
61 return false
62 }
63 for d := 2; d*d <= x; d++ {
64 if x%d == 0 {
65 return false
66 }
67 }
68 return true
69}
70
71// Render renders the sieve for gnoweb.
72//
73// Render("") / Render("/") -> first 100 primes + total count up to MaxN
74// Render("/<n>") -> every prime <= n, laid out as a grid
75func Render(path string) string {
76 n, hasN := parseN(path)
77
78 var b strings.Builder
79 b.WriteString("# Sieve of Eratosthenes\n\n")
80 b.WriteString("A deterministic on-chain port of Go's classic concurrent prime-sieve example.\n\n")
81
82 if !hasN {
83 primes := PrimesUpTo(MaxN)
84 b.WriteString("There are **")
85 b.WriteString(strconv.Itoa(len(primes)))
86 b.WriteString("** primes up to ")
87 b.WriteString(strconv.Itoa(MaxN))
88 b.WriteString(".\n\n")
89 b.WriteString("## First 100 primes\n\n")
90 first := primes
91 if len(first) > 100 {
92 first = first[:100]
93 }
94 b.WriteString(grid(first, 10))
95 b.WriteString("\n> Try `/500` or `/1000` to sieve up to any n (max ")
96 b.WriteString(strconv.Itoa(MaxN))
97 b.WriteString(").\n")
98 return b.String()
99 }
100
101 if n < 2 {
102 b.WriteString("No primes <= ")
103 b.WriteString(strconv.Itoa(n))
104 b.WriteString(".\n")
105 return b.String()
106 }
107
108 clamped := n
109 if clamped > MaxN {
110 clamped = MaxN
111 }
112 primes := PrimesUpTo(clamped)
113 b.WriteString("## Primes up to ")
114 b.WriteString(strconv.Itoa(clamped))
115 if clamped != n {
116 b.WriteString(" (clamped from ")
117 b.WriteString(strconv.Itoa(n))
118 b.WriteString(")")
119 }
120 b.WriteString("\n\n")
121 b.WriteString("Count: **")
122 b.WriteString(strconv.Itoa(len(primes)))
123 b.WriteString("**\n\n")
124 b.WriteString(grid(primes, 10))
125 return b.String()
126}
127
128// parseN extracts n from a Render path like "/1000". Returns hasN=false for
129// the empty/root path.
130func parseN(path string) (int, bool) {
131 s := strings.TrimSpace(path)
132 s = strings.TrimPrefix(s, "/")
133 if s == "" {
134 return 0, false
135 }
136 // keep only the first segment
137 if i := strings.IndexByte(s, '/'); i >= 0 {
138 s = s[:i]
139 }
140 v, err := strconv.Atoi(s)
141 if err != nil {
142 return 0, false
143 }
144 return v, true
145}
146
147// grid formats primes into a Markdown table with `cols` columns per row.
148func grid(primes []int, cols int) string {
149 if len(primes) == 0 {
150 return "_none_\n"
151 }
152 if cols < 1 {
153 cols = 1
154 }
155
156 var b strings.Builder
157 // header + separator so gnoweb renders it as a table
158 b.WriteString("|")
159 for c := 0; c < cols; c++ {
160 b.WriteString(" · |")
161 }
162 b.WriteString("\n|")
163 for c := 0; c < cols; c++ {
164 b.WriteString("---|")
165 }
166 b.WriteString("\n")
167
168 for i := 0; i < len(primes); i += cols {
169 b.WriteString("|")
170 for c := 0; c < cols; c++ {
171 b.WriteString(" ")
172 if i+c < len(primes) {
173 b.WriteString(strconv.Itoa(primes[i+c]))
174 }
175 b.WriteString(" |")
176 }
177 b.WriteString("\n")
178 }
179 return b.String()
180}
