Category talk:Wren-math: Difference between revisions

Content added Content deleted

Inline

@@ Line 191: / Line 191: @@
     // Convenience version of above method which uses true for the primesOnly parameter.
     static primeSieve(n) { primeSieve(n, true) }
+    // Sieves for primes up to and including 'limit' using a segmented approach
+    // and returns a list of the primes found in order.
+    // Second argument needs to be the cache size (L1) of your machine in bytes.
+    // Translated from public domain C++ code at:
+    // https://gist.github.com/kimwalisch/3dc39786fab8d5b34fee
+    static segmentedSieve(limit, cacheSize) {
+        cacheSize = (cacheSize/8).floor // 8 bytes per list element
+        var sqroot = limit.sqrt.floor
+        var segSize = sqroot.max(cacheSize)
+        if (limit < 2) return []
+        var allPrimes = [2]
+        var isPrime = List.filled(sqroot + 1, true)
+        var primes  = []
+        var multiples = []
+        var i = 3
+        var n = 3
+        var s = 3
+        var low = 0
+        while (low <= limit) {
+            var sieve = List.filled(segSize, true)
+            var high = limit.min(low + segSize - 1)
+            while (i * i <= high) {
+                if (isPrime[i]) {
+                    var j = i * i
+                    while (j <= sqroot) {
+                        isPrime[j] = false
+                        j = j + i
+                    }
+                }
+                i = i + 2
+            }
+            while (s * s <= high) {
+                if (isPrime[s]) {
+                    primes.add(s)
+                    multiples.add(s * s - low)
+                }
+                s = s + 2
+            }
+            for (ii in 0...primes.count) {
+                var j = multiples[ii]
+                var k = primes[ii] * 2
+                while (j < segSize) {
+                    sieve[j] = false
+                    j = j + k
+                }
+                multiples[ii] = j - segSize
+            }
+            while (n <= high) {
+                if (sieve[n - low]) allPrimes.add(n)
+                n = n + 2
+            }
+            low = low + segSize
+        }
+        return allPrimes
+    }
     // Private helper method which counts and returns how many primes there are