Category talk:Go-rcu: Difference between revisions

Content added Content deleted

Inline

@@ Line 2: / Line 2: @@
 <lang go>package rcu
-import "fmt"
+import (
+    "fmt"
+    "rcu"
+)
 // Returns the larger of two ints.
@@ Line 111: / Line 114: @@
     }
     return primes
+}
+// Sieves for primes up to and including 'n' and returns how many there are.
+// Uses an algorithm better suited to counting than the one used in the PrimeSieve method.
+func PrimeCount(n int) int {
+    if n < 2 {
+        return 0
+    }
+    count := 1
+    k := (n-3)/2 + 1
+    marked := make([]bool, k) // all false by default
+    limit := (int(math.Sqrt(float64(n)))-3)/2 + 1
+    for i := 0; i < limit; i++ {
+        if !marked[i] {
+            p := 2*i + 3
+            s := (p*p - 3) / 2
+            for j := s; j < k; j += p {
+                marked[j] = true
+            }
+        }
+    }
+    for i := 0; i < k; i++ {
+        if !marked[i] {
+            count++
+        }
+    }
+    return count
 }