Generate Prime Pairs for Goldbach's Conjecture

# Enable YJIT if using CRuby >= 3.3"
RubyVM::YJIT.enable if RUBY_ENGINE == "ruby" and RUBY_VERSION.to_f >= 3.3

def prime_pairs_lohi(n)
  return puts "Input not even n > 2" unless n.even? && n > 2
  return (pp [n, 1]; pp [n/2, n/2]; pp [n/2, n/2]) if n <= 6

  # generate the low-half-residues (lhr) r < n/2
  lhr = 3.step(n/2, 2).select { |r| r if r.gcd(n) == 1 }
  ndiv2, rhi = n/2, n-2            # lhr:hhr midpoint, max residue limit
  lhr_mults = []                   # for lhr values not part of a pcp

  # store all the powers of the lhr members < n-2
  lhr.each do |r|                  # step thru the lhr members
    r_pwr = r                      # set to first power of r
    break if r > rhi / r_pwr       # exit if r^2 > n-2, as all others are too
    while    r < rhi / r_pwr       # while r^e < n-2
      lhr_mults << (r_pwr *= r)    # store its current power of r
    end
  end

  # store all the cross-products of the lhr members < n-2
  lhr_dup = lhr.dup                # make copy of the lhr members list
  while (r = lhr_dup.shift) && !lhr_dup.empty? # do mults of 1st list r w/others
    ri_max = rhi / r               # ri can't multiply r with values > this
    break if lhr_dup[0] > ri_max   # exit if product of consecutive r’s > n-2
    lhr_dup.each do |ri|           # for each residue in reduced list
      break if ri > ri_max         # exit for r if cross-product with ri > n-2
      lhr_mults << r * ri          # store value if < n-2
    end                            # check cross-products of next lhr member
  end

  # 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 = lhr_mults.map { |r_del| (r_del > ndiv2 ? n - r_del : r_del) }

  pp [n, (lhr -= lhr_del).size]    # show n and pcp prime pairs count
  pp [lhr.first, n-lhr.first]      # show first pcp prime pair of n
  pp [lhr.last,  n-lhr.last]       # show last  pcp prime pair of n
end

def tm; t = Time.now; yield; Time.now - t end  # to time runtime execution

n = ARGV[0].to_i                   # get n value from terminal
puts tm { prime_pairs_lohi(n) }    # show execution runtime as last output

function prime_pairs_lohi(n)
  if (n&1 == 1 || n < 4) return println("Input not even n > 2") end
  if (n <= 6) println([n, 1]); println([div(n,2),div(n,2)]); println([div(n,2),div(n,2)]); return end

  # generate the low-half-residues (lhr) r < n/2
  ndiv2, rhi = div(n,2), n-2         # lhr:hhr midpoint, max residue limit
  lhr = []                           # array for low half residues
  for r in 3:2:ndiv2; if (gcd(r, n) == 1) append!(lhr, r) end end
  lhr_mults = []                     # for lhr values not part of a pcp

  # store all the powers of the lhr members < n-2
  for r in lhr                       # step thru the lhr members
    r_pwr = r                        # set to first power of r
    if (r > div(rhi, r_pwr)) break end # exit if r^2 > n-2, as all others are too
    while (r < div(rhi, r_pwr))      # while r^e < n-2
      r_pwr *= r                     # increase power of r
      append!(lhr_mults, r_pwr)      # store its current power of r
    end
  end

  # store all the cross-products of the lhr members < n-2
  i = 1; ln = length(lhr)
  while (i < ln)
    r = lhr[i]
    rmax = div(rhi, r)               # ri can't multiply r with values > this
    if (lhr[i+1] > rmax) break end   # exit if product of consecutive r’s > n-2
    j = i+1
    while (j < ln)                   # for each residue in reduced list
      ri = lhr[j]
      if (ri > rmax) break end       # exit for r if cross-product with ri > n-2
      append!(lhr_mults, r * ri)     # store value if < n-2
      j += 1
    end
    i += 1
  end

  # 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 = []
  for r in lhr_mults
    r_del = (r > ndiv2) ? n - r : r
    append!(lhr_del, r_del)
  end

  lhr = setdiff(lhr,lhr_del)         # remove lhr_del residues from lhr

  println([n,  length(lhr)])         # show n and pcp prime pairs count
  println([first(lhr),n-first(lhr)]) # show first pcp prime pair of n
  println([last(lhr), n-last(lhr)])  # show last  pcp prime pair of n
end


num = readline()                     # get n value from terminal
n = parse(Int64, num)
prime_pairs_lohi(n)                  # show execution runtime as last output
println()

➜  ~ ruby prime_pairs_lohi.rb 100_000_000
[100000000, 291400]
[11, 99999989]
[49999757, 50000243]
24.21507651

➜  ~ time julia prime_pairs_lohi.jl
100000000
[100000000, 291400]
[11, 99999989]
[49999757, 50000243]

julia prime_pairs_lohi.jl  39.54s user 3.68s system 87% cpu 49.275 total