Ramanujan primes: Difference between revisions

Content added Content deleted

Inline

@@ Line 131: / Line 131: @@
 =={{header|Go}}==
-{{trans|Wren}}
+{{trans|C++}}
 {{libheader|Go-rcu}}
+<br>
-A decent time though not as quick as Phix.
+This takes about 40 ms to find the 100,000th Ramanujan prime on my machine. The millionth takes about 520 ms.
 <lang go>package main
@@ Line 140: / Line 141: @@
     "math"
     "rcu"
-    "sort"
     "time"
 )
-var start = time.Now()
+var count []int
+func primeCounter(limit int) {
-var primes = rcu.Primes(700000) // say
+    count = make([]int, limit)
+    for i := 0; i < limit; i++ {
+        count[i] = 1
+    }
+    if limit > 0 {
+        count[0] = 0
+    }
+    if limit > 1 {
+        count[1] = 0
+    }
+    for i := 4; i < limit; i += 2 {
+        count[i] = 0
+    }
+    for p, sq := 3, 9; sq < limit; p += 2 {
+        if count[p] != 0 {
+            for q := sq; q < limit; q += p << 1 {
+                count[q] = 0
+            }
+        }
+        sq += (p + 1) << 2
+    }
+    sum := 0
+    for i := 0; i < limit; i++ {
+        sum += count[i]
+        count[i] = sum
+    }
+}
-func ramanujan(n int) int {
+func primeCount(n int) int {
+    if n < 1 {
+        return 0
+    }
+    return count[n]
+}
+func ramanujanMax(n int) int {
     fn := float64(n)
-    max := int(4 * fn * math.Log(4*fn) / math.Ln2)
+    return int(math.Ceil(4 * fn * math.Log(4*fn)))
+}
-    pi := sort.SearchInts(primes[2*n:], max) // binary search from min of (2n)th prime
-    for {
+func ramanujanPrime(n int) int {
-        if pi+1-rcu.PrimeCount(primes[pi]/2) <= n {
-            return primes[pi]
+    if n == 1 {
+        return 2
+    }
+    for i := ramanujanMax(n); i >= 2*n; i-- {
+        if i%2 == 1 {
+            continue
+        }
+        if primeCount(i)-primeCount(i/2) < n {
+            return i + 1
         }
-        pi--
     }
     return 0
@@ Line 162: / Line 203: @@
 func main() {
+    start := time.Now()
+    primeCounter(1 + ramanujanMax(1e6))
     fmt.Println("The first 100 Ramanujan primes are:")
     rams := make([]int, 100)
     for n := 0; n < 100; n++ {
-        rams[n] = ramanujan(n + 1)
+        rams[n] = ramanujanPrime(n + 1)
     }
     for i, r := range rams {
@@ Line 174: / Line 217: @@
     }
-    fmt.Printf("\nThe 1,000th Ramanujan prime is %6s\n", rcu.Commatize(ramanujan(1000)))
+    fmt.Printf("\nThe 1,000th Ramanujan prime is %6s\n", rcu.Commatize(ramanujanPrime(1000)))
-    fmt.Printf("\nThe 10,000th Ramanujan prime is %7s\n", rcu.Commatize(ramanujan(10000)))
+    fmt.Printf("\nThe 10,000th Ramanujan prime is %7s\n", rcu.Commatize(ramanujanPrime(10000)))
+    fmt.Printf("\nThe 100,000th Ramanujan prime is %6s\n", rcu.Commatize(ramanujanPrime(100000)))
+    fmt.Printf("\nThe 1,000,000th Ramanujan prime is %7s\n", rcu.Commatize(ramanujanPrime(1000000)))
     fmt.Println("\nTook", time.Since(start))
@@ Line 199: / Line 246: @@
 The 10,000th Ramanujan prime is 242,057
+The 100,000th Ramanujan prime is 2,916,539
-Took 946.193311ms
+The 1,000,000th Ramanujan prime is 34,072,993
+Took 519.655163ms
 </pre>