Goldbach's Conjecture and Crystal Code

Help & Support
48

Here’s the Go version. Go isn’t really designed for intensive numerical computing.
It doesn’t handle the removal of elements in one array from another very fast.
For n > 1,000,000 performance really drops.

// Compile as: $ go build prime_pairs_lohi.go
// Run as: $ ./prime_pairs_lohi 123_456

package main

import (
  "os"
  "fmt"
  "time"
  "slices"
  "strconv"
  "strings"
)

func coprime(m, n uint) bool {
  for m | 1 != 1 { m, n = n % m, m }
  return (m > 0)
}

func prime_pairs_lohi(n uint) {
  if n&1 == 1 || n < 4 {fmt.Printf("Input not even n > 2"); return }
  if n <= 6 { fmt.Printf("[%d, %d]\n[%d, %d]\n[%d, %d]\n",n,1,n/2,n/2,n/2,n/2); return }

  // generate the low-half-residues (lhr) r < n/2
  ndiv2, rhi := n/2, n-2                    // lhr:hhr midpoint, max residue limit
  lhr := []uint{}                           // to store low half residues
  var r uint = 3
  for r < ndiv2 {if coprime(r, n) { lhr = append(lhr, r)}; r += 2 }

  // identify and store all powers and cross-products of the lhr members < n-2
  lhr_mults := []uint{}                     // lhr multiples, not part of a pcp
  for i := 1; i < len(lhr)-1; i++ {         // iterate thru lhr to find prime multiples
    r := lhr[i-1]                           // for current residue
    rmax := rhi / r                         // ri can't multiply r with values > this
    if r < rmax {lhr_mults = append(lhr_mults, r * r)}  // for r^2 multiples
    if lhr[i] > rmax { break }              // exit if product of consecutive r’s > n-2
    for j := i; j < len(lhr)-1; j++ {       // iterate thru lhr to find prime multiples
      if lhr[j] > rmax { break }            // exit for r if cross-product with ri > n-2
      lhr_mults = append(lhr_mults, r * lhr[j]) // store value if < n-2
  } }

  // convert lhr_mults vals > n/2 to their lhr complements n-r,
  // store them, those < n/2, in lhr_del; it now holds non-pcp lhr vals
  lhr_del := []uint{}
  for _, r := range(lhr_mults) {if r > ndiv2 {r = n - r}; lhr_del = append(lhr_del, r)}
  lhr = slices.DeleteFunc(lhr, func(n uint) bool { return slices.Contains(lhr_del, n) })

  lcnt := len(lhr)
  fmt.Printf("[%d, %d]\n", n, lcnt)                    // show n and pcp prime pairs count
  fmt.Printf("[%d, %d]\n", lhr[0],n-lhr[0])            // show first pcp prime pair of n
  fmt.Printf("[%d, %d]\n", lhr[lcnt-1], n-lhr[lcnt-1]) // show last  pcp prime pair of n
}

func main() {
  s := os.Args[1]
  num := strings.Replace(s, "_", "", -1)
  n, err := strconv.ParseUint(num, 10, 64)
  if err != nil {panic(err)}

  ts := time.Now()
  prime_pairs_lohi(uint(n))
  te := time.Now()
  fmt.Printf("%v",te.Sub(ts))
}