On Monday, 3 February 2025 at 00:04:17 UTC, Sergey wrote:

Good idea. I'll see if I'm up to it.

Another code opt for you.

I translated this Ruby code:

  lhr_del = lhr_mults.map { |r_del| (r_del > ndiv2 ? n - r_del : r_del) }

  lhr_rmax = Integer.sqrt(n-2) + 2                 # the lhr_rmax high bound
  lhr_rmax_cnt = lhr.count { |r| r <= lhr_rmax }   # count of lhr <= lhr_rmax
  lhr -= lhr_del                                   # lhr pcp prime residues
  pcp_rmax = lhr.select { |r| r if r <= lhr_rmax } # lhr pcp prime residues <= lhr_rmax

To this D code. It works, seems fast, can it be done shorter, faster, more idiomatic?

  auto lhr_del = lhr_mults.map!((r_del) => r_del > ndiv2 ? n - r_del : r_del).array;
  lhr_del.sort!("a < b");

  auto lhr_rmax = 2 + cast(uint) sqrt(cast(double) n-2);
  auto lhr_rmax_cnt = 0;
  foreach(r; lhr) { if (r > lhr_rmax) break; lhr_rmax_cnt += 1;}
  lhr = setDifference(lhr, lhr_del).array;
  uint[] pcp_rmax;
  foreach(pcp; lhr) { if (pcp > lhr_rmax) break; pcp_rmax ~= pcp; }

On Monday, 3 February 2025 at 04:15:09 UTC, Jabari Zakiya wrote:

translated code isnt going to be idiomatic ever; just state what you want done

On Monday, 3 February 2025 at 04:59:43 UTC, monkyyy wrote:

FYI.
This code finds all the prime pairs that sum to n for all even integers n > 2.
It (Ruby code) is included in a paper I just released (Feb 2, 2025) on Goldbach's Conjecture (1742) and Bertrand's Postulate (1845). For those interested in Prime|Number Theory check it out. A lot of new, good, stuff is in it!

Proof of Goldbach's Conjecture and Bertrand's Postulate Using Prime Generator Theory (PGT)

https://www.academia.edu/127404211/Proof_of_Goldbachs_Conjecture_and_Bertrands_Postulate_Using_Prime_Generator_Theory_PGT_

On Tuesday, 4 February 2025 at 17:17:42 UTC, Jabari Zakiya wrote:

I updated the code to make entering data easier.
It now mimics the Ruby|Crystal code and takes "humanized" data strings.
You can now run the code as: $ ./primes_pair_lohi_u32 123_456_780

I also created two versions, one for u32 input values, and one for u64.
Unless you have lots of memmory, the u32 version is best to use.

Here's the u32 input size version.

// Compile with ldc2: $ ldc2 --release -O3 -mcpu native prime_pairs_lohi_u32.d
// Run as: $ ./prime_pairs_lohi_u32 123_456_780

module prime_pairs;

import std;
import std.datetime.stopwatch : StopWatch;

void prime_pairs_lohi(uint n) {   // inputs can be of size u32
  if ((n&1) == 1 || n < 4) { return writeln("Input not even n > 2"); }
  if (n <= 6) { writeln([n, 1]); writeln([n/2, n/2]); writeln([n/2, n/2]); return; }

  // generate the low-half-residues (lhr) r < n/2
  auto ndiv2 = n/2;               // llr:hhr midpoint
  auto rhi   = n-2;               // max residue limit
  uint[] lhr = iota(3, ndiv2, 2).filter!(e => gcd(e, n) == 1).array;

  // store all the powers of the lhr members < n-2
  uint[] lhr_mults;               // for lhr values not part of a pcp
  foreach(r; lhr) {               // step thru the lhr members
    auto r_pwr = r;               // set to first power of r
    if (r > rhi/r_pwr) break;     // 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 rA
  }

  // store all the cross-products of the lhr members < n-2
  foreach(i, r; lhr) {
    auto ri_max = rhi / r;        // ri can't multiply r with values > this
    if (lhr[i+1] > ri_max) break; // exit if product of consecutive r’s > n-2
    foreach(ri; lhr[i+1..$]) {    // for each residue in reduced list
      if (ri > ri_max) break;     // exit for r if cross-product with ri > n-2
      lhr_mults ~= r * ri;        // 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
  auto lhr_del = lhr_mults.map!((r_del) => r_del > ndiv2 ? n - r_del : r_del).array;
  lhr_del.sort!("a < b");
  lhr = setDifference(lhr, lhr_del).array;

  writeln([n,     lhr.length]);   // show n and pcp prime pairs count
  writeln([lhr[0],  n-lhr[0]]);   // show first pcp prime pair of n
  writeln([lhr[$-1],n-lhr[$-1]]); // show last  pcp prime pair of n
}

void main(string[] args) {        // directly recieve input from terminal
  string[] inputs = args[1..$];   // can include '_': 123_456
  auto nums = inputs.map!(i => i.filter!(n => n != '_'));
  auto n    = nums.map!(f => f.to!uint())[0];

  auto timer = StopWatch();       // create execution timer
  timer.start();                  // start it
  prime_pairs_lohi(n);            // run routine
  writeln(timer.peek());          // show timer results
}

Here's the u64 version.

// Compile with ldc2: $ ldc2 --release -O3 -mcpu native prime_pairs_lohi_u64.d
// Run as: $ ./prime_pairs_lohi_u64 123_456_780

module prime_pairs;

import std;
import std.datetime.stopwatch : StopWatch;

void prime_pairs_lohi(ulong n) {  // inputs can be of size u64
  if ((n&1) == 1 || n < 4) { return writeln("Input not even n > 2"); }
  if (n <= 6) { writeln([n, 1]); writeln([n/2, n/2]); writeln([n/2, n/2]); return; }

  // generate the low-half-residues (lhr) r < n/2
  auto ndiv2 = n/2;               // llr:hhr midpoint
  auto rhi   = n-2;               // max residue limit
  ulong[] lhr = iota(3, ndiv2, 2).filter!(e => gcd(e, n) == 1).array;

  // store all the powers of the lhr members < n-2
  ulong[] lhr_mults;              // for lhr values not part of a pcp
  foreach(r; lhr) {               // step thru the lhr members
    auto r_pwr = r;               // set to first power of r
    if (r > rhi/r_pwr) break;     // 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 rA
  }

  // store all the cross-products of the lhr members < n-2
  foreach(i, r; lhr) {
    auto ri_max = rhi / r;        // ri can't multiply r with values > this
    if (lhr[i+1] > ri_max) break; // exit if product of consecutive r’s > n-2
    foreach(ri; lhr[i+1..$]) {    // for each residue in reduced list
      if (ri > ri_max) break;     // exit for r if cross-product with ri > n-2
      lhr_mults ~= r * ri;        // 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
  auto lhr_del = lhr_mults.map!((r_del) => r_del > ndiv2 ? n - r_del : r_del).array;
  lhr_del.sort!("a < b");
  lhr = setDifference(lhr, lhr_del).array;

  writeln([n,     lhr.length]);   // show n and pcp prime pairs count
  writeln([lhr[0],  n-lhr[0]]);   // show first pcp prime pair of n
  writeln([lhr[$-1],n-lhr[$-1]]); // show last  pcp prime pair of n
}

void main(string[] args) {        // directly recieve input from terminal
  string[] inputs = args[1..$];   // can include '_': 123_456
  auto nums = inputs.map!(i => i.filter!(n => n != '_'));
  auto n    = nums.map!(f => f.to!ulong())[0];

  auto timer = StopWatch();       // create execution timer
  timer.start();                  // start it
  prime_pairs_lohi(n);            // run routine
  writeln(timer.peek());          // show timer results
}

On Wednesday, 5 February 2025 at 21:24:51 UTC, Jabari Zakiya wrote:

// Compile with ldc2: $ ldc2 --release -O3 -mcpu native prime_pairs_lohi_u32.d
// Run as: $ ./prime_pairs_lohi_u32 123_456_780

module prime_pairs;

import std;
import std.datetime.stopwatch : StopWatch;

void prime_pairs_lohi(uint n) {   // inputs can be of size u32
  if ((n&1) == 1 || n < 4) { return writeln("Input not even n > 2"); }
  if (n <= 6) { writeln([n, 1]); writeln([n/2, n/2]); writeln([n/2, n/2]); return; }

  // generate the low-half-residues (lhr) r < n/2
  auto ndiv2 = n/2;               // llr:hhr midpoint
  auto rhi   = n-2;               // max residue limit
  uint[] lhr = iota(3, ndiv2, 2).filter!(e => gcd(e, n) == 1).array;

  // store all the powers of the lhr members < n-2
  uint[] lhr_mults;               // for lhr values not part of a pcp
  foreach(r; lhr) {               // step thru the lhr members
    auto r_pwr = r;               // set to first power of r
    if (r > rhi/r_pwr) break;     // 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 rA
  }

  // store all the cross-products of the lhr members < n-2
  foreach(i, r; lhr) {
    auto ri_max = rhi / r;        // ri can't multiply r with values > this
    if (lhr[i+1] > ri_max) break; // exit if product of consecutive r’s > n-2
    foreach(ri; lhr[i+1..$]) {    // for each residue in reduced list
      if (ri > ri_max) break;     // exit for r if cross-product with ri > n-2
      lhr_mults ~= r * ri;        // 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
  auto lhr_del = lhr_mults.map!((r_del) => r_del > ndiv2 ? n - r_del : r_del).array;
  lhr_del.sort!("a < b");
  lhr = setDifference(lhr, lhr_del).array;

  writeln([n,     lhr.length]);   // show n and pcp prime pairs count
  writeln([lhr[0],  n-lhr[0]]);   // show first pcp prime pair of n
  writeln([lhr[$-1],n-lhr[$-1]]); // show last  pcp prime pair of n
}

void main(string[] args) {        // directly recieve input from terminal
  string[] inputs = args[1..$];   // can include '_': 123_456
  auto nums = inputs.map!(i => i.filter!(n => n != '_'));
  auto n    = nums.map!(f => f.to!uint())[0];

  auto timer = StopWatch();       // create execution timer
  timer.start();                  // start it
  prime_pairs_lohi(n);            // run routine
  writeln(timer.peek());          // show timer results
}

I've updated the code to make it shorter|simpler.

module prime_pairs;

import std;
import std.datetime.stopwatch : StopWatch;

void prime_pairs_lohi(uint n) {   // inputs can be of size u32
  if ((n&1) == 1 || n < 4) { return writeln("Input not even n > 2"); }
  if (n <= 6) { writeln([n, 1]); writeln([n/2, n/2]); writeln([n/2, n/2]); return; }

  // generate the low-half-residues (lhr) r < n/2
  auto ndiv2 = n/2;               // llr:hhr midpoint
  auto rhi   = n-2;               // max residue limit
  uint[] lhr = iota(3, ndiv2, 2).filter!(e => gcd(e, n) == 1).array;

  // store all powers and cross-products of the lhr members < n-2
  uint[] lhr_mults;               // lhr multiples, not part of a pcp
  foreach(i, r; lhr) {
    auto rmax = rhi / r;          // ri can't multiply r with values > this
    if (r < rmax) lhr_mults ~= r*r; // for r^2 multiples
    if (lhr[i+1] > rmax) break  ; // exit if product of consecutive r’s > n-2
    foreach(ri; lhr[i+1..$]) {    // for each residue in reduced list
      if (ri > rmax) break;       // exit for r if cross-product with ri > n-2
      lhr_mults ~= r * ri;        // 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
  auto lhr_del = lhr_mults.map!((r_del) => r_del > ndiv2 ? n - r_del : r_del).array;
  lhr_del.sort!("a < b");
  lhr = setDifference(lhr, lhr_del).array; // lhr now contains just pcp primes

  writeln([n,     lhr.length]);   // show n and pcp prime pairs count
  writeln([lhr[0],  n-lhr[0]]);   // show first pcp prime pair of n
  writeln([lhr[$-1],n-lhr[$-1]]); // show last  pcp prime pair of n
}

void main(string[] args) {        // directly recieve input from terminal
  string[] inputs = args[1..$];   // can include '_': 123_456
  auto nums = inputs.map!(i => i.filter!(n => n != '_'));
  auto n    = nums.map!(f => f.to!uint())[0];

  auto timer = StopWatch();       // create execution timer
  timer.start();                  // start it
  prime_pairs_lohi(n);            // run routine
  writeln(timer.peek());          // show timer results
}

  // 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
  auto lhr_del = lhr_mults.map!((r_del) => r_del > ndiv2 ? n - r_del : r_del).array;
  lhr_del.sort!("a < b");
  lhr = setDifference(lhr, lhr_del).array;

I'm bringing attention to this issue as it might improve D.

It has to do with the fastest way to remove elements in one array|list from another.

It concerns the code in this thread to generate the prime pairs of n.

In the code I have two arrays, lhr and lhr_del, and want to remove|delete the elements in lhr_del from lhr.

In D it's:
lhr_del.sort!("a < b");
lhr = setDifference(lhr, lhr_del).array;

In the original Rust version it was done as: lhr.retain(|&m| !lhr_del.contains(&m));

This is conceptually keeping the members in lhr not in lhr_del.

This is slow in Rust, and was greatly improved doing:

lhr_del.sort_unstable();
lhr.retain(|&m| !lhr_del.binary_search(&m).is_ok());

Then Someone did a Rust equivalent of D's setDifference allowing it to be coded as:

lhr_del.sort_unstable();
let lhr: Vec<u32> = SetDiff::new(&lhr, &lhr_del).collect();

This is even faster. Here's the Rust code implementation for the u32 version.
Change the u32 references to usize for u64 size numbers (which use more memory).

struct SetDiff<'a> {
  r1: &'a [u32],
  r2: &'a [u32],
}

impl<'a> SetDiff<'a> {
  fn adjust_pos(&mut self) {
    while !self.r1.is_empty() {
      if self.r2.is_empty() || self.r1[0] < self.r2[0] {
        break;
      } else if self.r2[0] < self.r1 [0] {
        self.r2 = &self.r2[1..];
      } else {
        self.r1 = &self.r1[1..];
        self.r2 = &self.r2[1..];
  } } }

  fn new(r1: &'a [u32], r2: &'a [u32]) -> Self {
    let mut s = SetDiff{ r1, r2 };
    s.adjust_pos();
    s
} }

impl<'a> Iterator for SetDiff<'a> {
  type Item = u32;

  fn next(&mut self) -> Option<Self::Item> {
    let val = self.r1.get(0).copied();
    if val.is_some() {
      self.r1 = &self.r1[1..];
    }
    self.adjust_pos();
    return val
} }

Here are u32 time comparisons for the last two Rust versions and D.

------------------------------------------
       n      | b-srch | setdif |   D    |
------------_-|--------|--------|--------|
  100,000,000 |  3.35  |  2.96  |  7.21  |
--------------|--------|------- |--------|
  200,000,000 |  7.77  |  6.19  | 15.86  |
------- ------|--------|--------|--------|
  300,000,000 |  6.40  |  5.73  | 10.89  |
--------------|--------|--------|--------|
  400,000,000 | 14.44  | 12.80  | 33.13  |
---- ---------|--------|--------|--------|
  500,000,000 | 18.44  | 16.32  | 42.58  |
--------------|--------|--------|--------|
  600,000,000 | 13.47  | 12.05  | 22.22  |
---- ---------|--------|--------|--------|
  700,000,000 | 21.72  | 19.51  | 46.19  |
--------------|--------|--------|--------|
  800,000,000 | 30.97  | 27.51  | 71.44  |
---- ---------|--------|--------|--------|
  900,000,000 | 22.95  | 18.30  | 35.66  |
--------------|--------|--------|--------|
1,000,000,000 | 38.99  | 34.81  | 88.74  |

The only substantive difference between the versions seems to be how each does its SetDif.
At least that's the only thing I can think of that causes this much performance difference.

I thought I'd let you know.

Here are the source files, and compiling settings.

/*
  D LDC2 1.40
  Compile with ldc2: $ ldc2 --release -O3 -mcpu native prime_pairs_lohi.d
  Run as: $ ./prime_pairs_lohi_u32 123_456
*/

module prime_pairs;

import std;
import std.datetime.stopwatch : StopWatch;

void prime_pairs_lohi(uint n) {     // inputs can be of size u32
  if ((n&1) == 1 || n < 4) { return writeln("Input not even n > 2"); }
  if (n <= 6) { writeln([n, 1]); writeln([n/2, n/2]); writeln([n/2, n/2]); return; }

  // generate the low-half-residues (lhr) r < n/2
  auto ndiv2 = n/2;                 // llr:hhr midpoint
  auto rhi   = n-2;                 // max residue limit
  uint[] lhr = iota(3, ndiv2, 2).filter!(e => gcd(e, n) == 1).array;

  // identify and store all powers and cross-products of the lhr members < n-2
  uint[] lhr_del;                   // lhr multiples, not part of a pcp
  foreach(i, r; lhr) {              // iterate thru lhr to find prime multiples
    auto rmax = rhi / r;            // ri can't multiply r with values > this
    if (r < rmax) lhr_del ~= (r*r < ndiv2) ? r*r : n - r*r; // for r^2 multiples
    if (lhr[i+1] > rmax) break  ;   // exit if product of consecutive r’s > n-2
    foreach(ri; lhr[i+1..$]) {      // for each residue in reduced list
      if (ri > rmax) break;         // exit for r if cross-product with ri > n-2
      lhr_del ~= (r*ri < ndiv2) ? r*ri : n - r*ri;         // store value if < n-2
  } }

  // remove from lhr its lhr mulitples, the pcp remain
  lhr_del.sort!("a < b");
  lhr = setDifference(lhr, lhr_del).array;

  writeln([n,     lhr.length]);     // show n and pcp prime pairs count
  writeln([lhr[0],  n-lhr[0]]);     // show first pcp prime pair of n
  writeln([lhr[$-1],n-lhr[$-1]]);   // show last  pcp prime pair of n
}

void main(string[] args) {          // directly recieve input from terminal
  string[] inputs = args[1..$];     // can include '_': 123_456
  auto nums = inputs.map!(i => i.filter!(n => n != '_'));
  auto n    = nums.map!(f => f.to!uint())[0];

  auto timer = StopWatch();         // create execution timer
  timer.start();                    // start it
  prime_pairs_lohi(n);              // run routine
  writeln(timer.peek());            // show timer results
}
------------------------------------------------------------------------------------
/*
   Rust 1.84.1
   Can compile as: $ cargo build --release
   or: $ RUSTFLAGS="-C opt-level=3 -C debuginfo=0 -C target-cpu=native" cargo build --release
   Run as: $ ./prime_pairs_lohi 123_456
*/

use std::time::Instant;

fn coprime(mut m: u32, mut n: u32) -> bool {
  while m|1 != 1 { let t = m; m = n % m; n = t }
  m > 0
}

fn prime_pairs_lohi(n : u32) {               // for u32 input values
  if n&1 == 1 || n < 4 { return println!("Input not even n > 2"); }
  if n <= 6 { return println!("[{}, {}]\n[{}, {}]\n[{}, {}]",n,1,n/2,n/2,n/2,n/2); };

  // generate the low-half-residues (lhr) r < n/2
  let (ndiv2, rhi) = (n/2, n-2);             // lhr:hhr midpoint, max residue limit
  let mut lhr: Vec<u32> = (3..ndiv2).step_by(2).filter(|&r| coprime(r, n)).collect();

  // identify and store all powers and cross-products of the lhr members < n-2
  let mut lhr_del = Vec::with_capacity(lhr.len() as usize);
  for i in 1..lhr.len()-1 {                  // iterate thru lhr to find prime multiples
    let (mut j, r) = (i, lhr[i-1]);          // for current residue
    let rmax = rhi / r;                      // ri can't multiply r with values > this
    if r < rmax { lhr_del.push(if r*r < ndiv2 {r*r} else {n - r*r} ); }
    if lhr[i] > rmax { break }               // exit if product of consecutive r’s > n-2
    while lhr[j] <= rmax {                   // stop for r if product with ri > n-2
      lhr_del.push(if r*lhr[j] < ndiv2 {r*lhr[j]} else {n - r*lhr[j]});
      j += 1;                                // get next lhr value
  } }

  lhr_del.sort_unstable();                   // remove from lhr its lhr mults
  lhr.retain(|&m| !lhr_del.binary_search(&m).is_ok());
  let lcnt = lhr.len();                      // number of pcp prime pairs
  println!("[{}, {}]", n, lcnt);             // show n and pcp prime pairs count
  println!("[{}, {}]", lhr[0],n-lhr[0]);     // show first pcp prime pair of n
  println!("[{}, {}]", lhr[lcnt-1], n-lhr[lcnt-1]); // show last  pcp prime pair of n
}

fn main() {
  let n: u32 = std::env::args()
    .nth(1).expect("missing count argument")
    .replace('_', "").parse().expect("one input");

  let start = Instant::now();
  prime_pairs_lohi(n);
  println!("{:?}", start.elapsed());
}
---------------------------------------------------------------------------------------------
/*
   Rust 1.84.1
   Can compile as: $ cargo build --release
   or: $ RUSTFLAGS="-C opt-level=3 -C debuginfo=0 -C target-cpu=native" cargo build --release
   Run as: $ ./prime_pairs_lohi 123_456
*/

use std::time::Instant;

struct SetDiff<'a> {
  r1: &'a [u32],
  r2: &'a [u32],
}

impl<'a> SetDiff<'a> {
  fn adjust_pos(&mut self) {
    while !self.r1.is_empty() {
      if self.r2.is_empty() || self.r1[0] < self.r2[0] {
        break;
      } else if self.r2[0] < self.r1 [0] {
        self.r2 = &self.r2[1..];
      } else {
        self.r1 = &self.r1[1..];
        self.r2 = &self.r2[1..];
  } } }

  fn new(r1: &'a [u32], r2: &'a [u32]) -> Self {
    let mut s = SetDiff{ r1, r2 };
    s.adjust_pos();
    s
} }

impl<'a> Iterator for SetDiff<'a> {
  type Item = u32;

  fn next(&mut self) -> Option<Self::Item> {
    let val = self.r1.get(0).copied();
    if val.is_some() {
      self.r1 = &self.r1[1..];
    }
    self.adjust_pos();
    return val
} }

fn coprime(mut m: u32, mut n: u32) -> bool {
  while m|1 != 1 { let t = m; m = n % m; n = t }
  m > 0
}

fn prime_pairs_lohi(n : u32) {               // for u32 input values
  if n&1 == 1 || n < 4 { return println!("Input not even n > 2"); }
  if n <= 6 { return println!("[{}, {}]\n[{}, {}]\n[{}, {}]",n,1,n/2,n/2,n/2,n/2); };

  // generate the low-half-residues (lhr) r < n/2
  let (ndiv2, rhi) = (n/2, n-2);             // lhr:hhr midpoint, max residue limit
  let mut lhr: Vec<u32> = (3..ndiv2).step_by(2).filter(|&r| coprime(r, n)).collect();

  // identify and store all powers and cross-products of the lhr members < n-2
  let mut lhr_del = Vec::with_capacity(lhr.len() as usize);
  for i in 1..lhr.len()-1 {                  // iterate thru lhr to find prime multiples
    let (mut j, r) = (i, lhr[i-1]);          // for current residue
    let rmax = rhi / r;                      // ri can't multiply r with values > this
    if r < rmax { lhr_del.push(if r*r < ndiv2 {r*r} else {n - r*r} ); }
    if lhr[i] > rmax { break }               // exit if product of consecutive r’s > n-2
    while lhr[j] <= rmax {                   // stop for r if product with ri > n-2
      lhr_del.push(if r*lhr[j] < ndiv2 {r*lhr[j]} else {n - r*lhr[j]});
      j += 1;                                // get next lhr value
  } }

  lhr_del.sort_unstable();                   // remove from lhr its lhr mults
  let lhr: Vec<u32> = SetDiff::new(&lhr, &lhr_del).collect();
  let lcnt = lhr.len();                      // number of pcp prime pairs
  println!("[{}, {}]", n, lcnt);             // show n and pcp prime pairs count
  println!("[{}, {}]", lhr[0],n-lhr[0]);     // show first pcp prime pair of n
  println!("[{}, {}]", lhr[lcnt-1], n-lhr[lcnt-1]); // show last  pcp prime pair of n
}

fn main() {
  let n: u32 = std::env::args()
    .nth(1).expect("missing count argument")
    .replace('_', "").parse().expect("one input");

  let start = Instant::now();
  prime_pairs_lohi(n);
  println!("{:?}", start.elapsed());
}

On Tuesday, 18 February 2025 at 22:45:39 UTC, Jabari Zakiya wrote:

Known issue with upstream, try one of mine data structures

https://github.com/opendlang/d/blob/main/source/odc/datastructures.d

On Tuesday, 18 February 2025 at 22:45:39 UTC, Jabari Zakiya wrote:

Many parts of the core code can be optimized. Since I don't have much time right now, I only saw 1 improvement. Below the GCD filter will give the same list (lhr[]).

  uint[] lhr;// = iota(3, ndiv2, 2).filter!(e => gcd(e, n) == 1).array;/*
  lhr.reserve(cast(ulong)log(cast(double)n)/2);
  for (uint i = 3; i < ndiv2; i += 2)
  {
    if (i % 3 != 0 && i % 5 != 0)
    {
      lhr ~= i;
    }
  }//*/

SDB@79

On Wednesday, 19 February 2025 at 02:25:03 UTC, Salih Dincer wrote:

It is giving different result

On Friday, 31 January 2025 at 20:05:54 UTC, Jabari Zakiya wrote:

First of all, I see that you don't use reserve() at all in arrays. Since I work on a mobile platform (by Dcoder from India), I have limited opportunities. So would you try the code below; does it work quickly, safely and with accurate results.

import std.stdio, std.conv, std.range, std.algorithm;
import std.datetime.stopwatch : StopWatch;

void main(string[] args)
{
  alias T = uint;
  auto inputs = ["5_005_446", "65_537"];
  auto nums   = inputs.map!(i => i.filter!(n => n != '_'));
  auto n      = nums.map!(f => f.to!T())[0];

  auto timer = StopWatch();
       timer.start();

       n.prime_pairs_lohi();
       timer.peek.writeln();
}

void prime_pairs_lohi(T)(T n)
{
  if (n & 1 || n < 4) { return writeln("Input not even n > 2"); }
  if (n <= 6) { writeln([n, 1]); writeln([n/2, n/2]); writeln([n/2, n/2]); return; }

  T ndiv2 = n / 2;
  T rhi   = n - 2;
  T[] lhr;// = iota(3, ndiv2, 2).filter!(e => gcd(e, n) == 1).array;/*
      lhr.reserve(n / 4); // SDB@79 added!

  auto factors = n.getFactors!100;
  for (T i = 3; i < ndiv2; i += 2)
  {
    bool coprime = true;
    foreach (p; factors)
    {
      if (i % p == 0)
      {
        coprime = false;
        break;
      }
    }
    if (coprime) lhr ~= i;
  }//*/

  // identify and store all powers and cross-products of the lhr members < n-2
  T[] lhr_del;                      // lhr multiples, not part of a pcp
      lhr_del.reserve(n / 2); // SDB@79 added!

  foreach(i, r; lhr) {              // iterate thru lhr to find prime multiples
    auto rmax = rhi / r;            // ri can't multiply r with values > this
    if (r < rmax) lhr_del ~= (r*r < ndiv2) ? r*r : n - r*r; // for r^2 multiples
    if (lhr[i+1] > rmax) break;     // exit if product of consecutive r’s > n-2
    foreach(ri; lhr[i+1..$]) {      // for each residue in reduced list
      if (ri > rmax) break;         // exit for r if cross-product with ri > n-2
      lhr_del ~= (r*ri < ndiv2) ? r*ri : n - r*ri;         // store value if < n-2
  } }

  // remove from lhr its lhr multiples, the pcp remain
  lhr_del.sort!"a < b";
  lhr = setDifference(lhr, lhr_del).array;

  writeln([n,     lhr.length]);     // show n and pcp prime pairs count
  writeln([lhr[0],  n-lhr[0]]);     // show first pcp prime pair of n
  writeln([lhr[$-1],n-lhr[$-1]]);   // show last  pcp prime pair of n
}

auto getFactors(int limit, T)(T n)
{
  T[] factors;
  T f = 3;
  T x = n;/*
  T x = n;
  while (x % 2 == 0) {
    factors ~= 2;
          x /= 2;
  }//*/
  while (f < limit && f * f <= x)
  {
    if (x % f == 0)
    {
      if (!factors.canFind(f))
      {
        factors ~= f;
      }
      x /= f;
    } else {
      f += 2;
    }
  }
  //if (x > 1) factors ~= x;

  return factors;
}

auto gcd(T)(T a, T b)
{
  while (b != 0)
  {
    auto temp = b;
    //while (a >= b) a -= b;/*
    a %= b; //*/
    b = a;
    a = temp;
  }
  return cast(T)a;
}

SDB@79