On Wednesday, 19 February 2025 at 23:58:09 UTC, Salih Dincer wrote:

I removed 1 line in your code (note if (r <= rMax) ) and added values ​​greater than 0 to the 2nd array (lhr_del[]). setDifference() did not cause any problems. Can you check?

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

void main(string[] args)
{
  alias T = uint;
  auto inputs = ["500_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();
} /*
[500005446, 1854807]
[7, 500005439]
[250002523, 250002923]
[250001387, 250004059]
[249999649, 250005797]
[249998743, 250006703]
1 minute, 44 secs, 656 ms, 912 μs, and 8 hnsecs

*/

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
  foreach(i, r; lhr) // iterate thru lhr to find prime multiples
  {
    auto rMax = rhi / r;
    if (r <= rMax)   // ri can't multiply r with values >= this
    {
      T r2 = r * r;  // for r^2 multiples
      if (auto value = (r2 < ndiv2) ? r2 : n - r2)
      { // SDB@79 added!
        lhr_del ~= value;
      }
    }
    // SDB@79 removed!
    // 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
      if (auto value = (r*ri < ndiv2) ? r*ri : n - r*ri) // store value if < n-2
      { // SDB@79 added!
        lhr_del ~= value;
      }
    }
  }

  // remove from lhr its lhr multiples, the pcp remain
  lhr = lhr.setDifference(lhr_del.sort!"a < b").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
  writeln([lhr[$-10], n-lhr[$-10]]);   // show last  pcp prime pair of n
  writeln([lhr[$-20], n-lhr[$-20]]);   // show last  pcp prime pair of n
  writeln([lhr[$-30], n-lhr[$-30]]);   // 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