Legendre prime counting function: Difference between revisions

Content added Content deleted

Inline

@@ Line 228: / Line 228: @@
 {{trans|Wren}}
 {{libheader|Go-rcu}}
+===Memoized===
 This runs in about 2.2 seconds which is surprisingly slow for Go. However, Go has the same problem as Wren in not being able to use lists for map keys. I tried using a 2-element array for the key but this was a second slower than the Cantor function.
@@ Line 290: / Line 291: @@
 ^8  5761455
 ^9  50847534
+</pre>
+===Non-memoized===
+Much quicker than before (0.53 seconds) and, of course, uses less memory.
+<syntaxhighlight lang="go">package main
+import (
+    "fmt"
+    "math"
+    "rcu"
+)
+func pi(n int) int {
+    if n < 2 {
+        return 0
+    }
+    if n == 2 {
+        return 1
+    }
+    primes := rcu.Primes(int(math.Sqrt(float64(n))))
+    a := len(primes)
+    var phi func(x, a int) int // recursive closure
+    phi = func(x, a int) int {
+        if a < 1 {
+            return x
+        }
+        if a == 1 {
+            return x - (x >> 1)
+        }
+        pa := primes[a-1]
+        if x <= pa {
+            return 1
+        }
+        return phi(x, a-1) - phi(x/pa, a-1)
+    }
+    return phi(n, a) + a - 1
+}
+func main() {
+    for i, n := 0, 1; i <= 9; i, n = i+1, n*10 {
+        fmt.Printf("10^%d  %d\n", i, pi(n))
+    }
+}</syntaxhighlight>
+{{out}}
+<pre>
+Same as first version.
 </pre>