I've hit my frustration limit, and would really like some help in improving this code.
The code finds all the prime pairs that sum to n for any even n > 2.
If you want an explanation of how|why it works read the following paper.
Proof of Goldbach's Conjecture and Bertrand's Postulate Using Prime Genrator Theory(GPT)
I'm sorry the Rust code is so bad, I'm not very proficient in it.
It works (gives correct results) but is horribly slow compared to the D|Crystal versions.
I suspect someone who knows Rust can make it the fastest.
Here is the D version (fastest so far).
// 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_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;
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 Crystal version (a bit slower).
# Compile: $ crystal build --release --mcpu native prime_pairs_lohi2.cr
# Run as: $ ./primes_pairs_lohi n 123_456_780
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 = 3u64.step(to: n//2, by: 2).select { |r| r if r.gcd(n) == 1 }.to_a
ndiv2, rhi = n//2, n-2 # lhr:hhr midpoint, max residue limit
# store all powers and cross-products of the lhr members < n-2
lhr_mults = [] of typeof(n) # lhr multiples, not part of a pcp
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
rmax = rhi // r # ri can't multiply r with values > this
lhr_mults << r * r if r < rmax # for r^2 multiples
break if lhr_dup[0] > rmax # exit if product of consecutive r’s > n-2
lhr_dup.each do |ri| # for each residue in reduced list
break if ri > rmax # 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
# remove from lhr its lhr_mults, convert vals > n/2 to lhr complements first
lhr -= lhr_mults.map { |r_del| r_del > ndiv2 ? n - r_del : r_del }
pp [n, lhr.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 gen_pcp
n = (ARGV[0].to_u64 underscore: true) # get n input from terminal
t1 = Time.monotonic # start execution timing
prime_pairs_lohi(n) # execute code
pp Time.monotonic - t1 # show execution time
end
gen_pcpAnd here's my current Rust version.
use std::time::Instant;
fn coprime(mut m: usize, mut n: usize) -> bool {
while m|1 != 1 { let t = m; m = n % m; n = t }
m > 0
}
fn prime_pairs_lohi(n : usize) {
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<usize> = vec![]; // to store low half residues
for r in (3..ndiv2).step_by(2) { if coprime(r, n) { lhr.push(r) } };
// indentify and store all powers and cross-products of the lhr members < n-2
let mut lhr_mults: Vec<usize> = vec![]; // lhr multiples, not part of a pcp
let mut lhr_dup = lhr.clone();
let mut r = lhr_dup[0];
lhr_dup.remove(0);
while !lhr_dup.is_empty() {
let rmax = rhi / r; // ri can't multiply r with values > this
if lhr_dup[0] > rmax { break } // exit if product of consecutive r’s > n-2
if r < rmax { lhr_mults.push(r * r)} // for r^2 multiples
for ri in &lhr_dup { // for each residue in reduced list
if *ri > rmax { break } // exit for r if cross-product with ri > n-2
lhr_mults.push(r * ri); // store value if < n-2
}
r = lhr_dup[0];
lhr_dup.remove(0);
}
// 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
let lhr_del: Vec<usize> = lhr_mults.into_iter().map(|r| if r > ndiv2 {n - r} else {r}).collect();
for r in lhr_del { lhr.retain(|&m| m != r)}; // remove lhr_mults values from lhr
let lcnt = lhr.len(); // number of lhr primes left
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 mut val = String::new();
std::io::stdin().read_line(&mut val).expect("Failed to read line");
let n: usize = val.trim().parse().unwrap();
let start = Instant::now();
prime_pairs_lohi(n);
println!("{:?}", start.elapsed());
}Thanks in advance for any help and suggestions.
Ah and btw, I only checked that it gives the same answer in my single test case, so please check correctness, if that code snippet is of interest!