diff --git i/Cargo.toml w/Cargo.toml
index c8dcf63..f26c811 100644
--- i/Cargo.toml
+++ w/Cargo.toml
@@ -1,10 +1,11 @@
[package]
name = "prime-factor"
description = "A prime number factorizer written in Rust"
-version = "0.6.3"
+version = "0.7.0"
authors = ["Stefan Lindblad <stefan.lindblad@linux.com>"]
license = "LGPL-2.1-or-later"
edition = "2024"
+homepage = "https://github.com/Fairglow/prime-factor"
repository = "https://github.com/Fairglow/prime-factor.git"
readme = "README.md"
diff --git i/benches/benchmark.rs w/benches/benchmark.rs
index ae42830..b6c8366 100644
--- i/benches/benchmark.rs
+++ w/benches/benchmark.rs
@@ -63,7 +63,7 @@ fn criterion_benchmark(c: &mut Criterion) {
fixed_grp.sample_size(10);
fixed_grp.bench_function("prime-factor lowest prime: 2", |b| b.iter(||
pf_number(2)));
- const FIXED_VEC: [(u8, u64, u128); 16] = [
+ const FIXED_VEC: [(u8, u64, u128); 23] = [
( 4, 1, 13),
( 8, 1, 251),
(12, 1, 4093),
@@ -76,11 +76,17 @@ fn criterion_benchmark(c: &mut Criterion) {
(40, 1, 1099511627689),
(44, 1, 17592186044399),
(48, 1, 281474976710597),
- (52, 2, 4503599627370449),
- (56, 9, 72057594037927931),
- (60, 36, 1152921504606846883),
- (64, 60, 18446744073709551557),
-// (68, 200, 295147905179352825833), // too slow, takes a few minutes, so we skip it
+ (52, 1, 4503599627370449),
+ (56, 1, 72057594037927931),
+ (60, 1, 1152921504606846883),
+ (64, 1, 18446744073709551557),
+ (68, 1, 295147905179352825833),
+ (70, 1, 1180591620717411303389),
+ (72, 1, 4722366482869645213603),
+ (74, 1, 18889465931478580854749),
+ (76, 1, 75557863725914323419121),
+ (78, 1, 302231454903657293676533),
+ (80, 1, 1208925819614629174706111),
];
for (bits, secs, prime) in FIXED_VEC.into_iter() {
fixed_grp.measurement_time(Duration::new(secs, 0));
diff --git i/justfile w/justfile
index 1ff83c3..6d48e74 100644
--- i/justfile
+++ w/justfile
@@ -10,22 +10,25 @@ alias t := tests
all: build test release
bench:
- cargo bench
+ unbuffer cargo bench | tee bench.log
-build:
- cargo build --all-targets && cargo clippy
+build: lint
+ unbuffer cargo build --all-targets | tee build.log
+
+lint:
+ unbuffer cargo clippy | tee lint.log
outdated:
cargo outdated --depth=1
reikna:
- cargo bench --bench bench-reikna --features bench-reikna
+ unbuffer cargo bench --bench bench-reikna --features bench-reikna | tee compare.log
release:
cargo build --release
test:
- cargo nextest run --test-threads num-cpus
+ unbuffer cargo nextest run --test-threads num-cpus | tee test.log
test-out:
cargo nextest run --no-capture --test-threads num-cpus
diff --git i/src/lib.rs w/src/lib.rs
index 31e1eee..4b5c2d6 100644
--- i/src/lib.rs
+++ w/src/lib.rs
@@ -135,23 +135,28 @@ impl PrimeFactors {
/// Compute the prime factorization of n using wheel factorization.
#[must_use]
pub fn factorize(n: u128) -> Self {
+ // If the number is large, we enable the Miller-Rabin fast paths
+ if n > MR_TRIAL_DIVISION_CROSSOVER {
+ Self::factorize_large(n)
+ } else {
+ // Hot path for small numbers: 100% pure trial division, no MR overhead
+ Self::factorize_small(n)
+ }
+ }
+ #[inline]
+ fn factorize_large(n: u128) -> Self {
let mut pf = PrimeFactors::new();
if n < 2 { return pf; }
+ let mut maxsq = n;
+ let mut x = n;
// --- 1. EARLY EXIT FOR PRIMES ---
- // If the number itself is prime, we don't need to do any trial division.
- // This drops the absolute worst-case scenario from hours down to nanoseconds!
- // We only use MR if n > 10 million where it beats standard division latency.
- if n > MR_TRIAL_DIVISION_CROSSOVER && u128_is_prime(n) {
+ if u128_is_prime(n) {
pf.add(n, 1);
return pf;
}
- let mut maxsq = n;
- let mut x = n;
let pw_iter = PrimeWheel::new();
for f in pw_iter {
- if f * f > maxsq {
- break;
- }
+ if f * f > maxsq { break; }
let mut c = 0;
while x.is_multiple_of(f) {
x /= f;
@@ -160,18 +165,39 @@ impl PrimeFactors {
if c > 0 {
maxsq = x;
pf.add(f, c);
- // --- 2. EARLY EXIT FOR INTERMEDIATE PRIMES ---
- // If we stripped out some factors and the remaining chunk 'x'
- // is proven prime by Miller-Rabin, we are fully done.
+ // --- 2. EARLY EXIT FOR INTERMEDIATE CHUNKS ---
if x > MR_TRIAL_DIVISION_CROSSOVER && u128_is_prime(x) {
pf.add(x, 1);
x = 1;
break;
}
}
- if x == 1 {
- break;
+ if x == 1 { break; }
+ }
+ if x > 1 {
+ pf.add(x, 1);
+ }
+ pf
+ }
+ #[inline]
+ fn factorize_small(n: u128) -> Self {
+ let mut pf = PrimeFactors::new();
+ if n < 2 { return pf; }
+ let mut maxsq = n;
+ let mut x = n;
+ let pw_iter = PrimeWheel::new();
+ for f in pw_iter {
+ if f * f > maxsq { break; }
+ let mut c = 0;
+ while x.is_multiple_of(f) {
+ x /= f;
+ c += 1;
+ }
+ if c > 0 {
+ maxsq = x;
+ pf.add(f, c);
}
+ if x == 1 { break; }
}
if x > 1 {
pf.add(x, 1);
@@ -255,7 +281,6 @@ impl Iterator for PrimeNumbers {
#[must_use]
pub fn u128_is_prime(n: u128) -> bool {
if !is_prime_candidate(n) { return false; }
-
// Trial division by subsequent small primes. Even though the wheel
// filters out multiples of 2, 3, 5, and 7, remaining composites are
// heavily stripped out by small integer division before hitting the
@@ -265,9 +290,8 @@ pub fn u128_is_prime(n: u128) -> bool {
];
for &p in SMALL_PRIMES {
if n == p { return true; }
- if n % p == 0 { return false; }
+ if n.is_multiple_of(p) { return false; }
}
-
if n < MR_DETERMINISTIC_LIMIT {
return miller_rabin(n);
}
diff --git i/src/main.rs w/src/main.rs
index 86ff9e7..9c1bdf8 100644
--- i/src/main.rs
+++ w/src/main.rs
@@ -2,7 +2,7 @@ use std::ops::RangeInclusive;
use clap::{Command, Arg, parser::ValuesRef};
use log::{debug, info};
use rayon::prelude::*;
-use primefactor::PrimeFactors;
+use primefactor::{PrimeFactors, PrimeNumbers, u128_is_prime};
const APPNAME: &str = env!("CARGO_PKG_NAME");
const VERSION: &str = env!("CARGO_PKG_VERSION");
@@ -18,10 +18,23 @@ fn main() {
.required(true)
.value_name("NUMBER")
.help("One or more numbers or ranges (e.g., 42, 100..200, 100..=200)"))
+ .arg(Arg::new("next")
+ .short('n')
+ .long("next")
+ .action(clap::ArgAction::SetTrue)
+ .help("Find the next prime number strictly greater than the given number(s)"))
+ .arg(Arg::new("prev")
+ .short('p')
+ .long("prev")
+ .action(clap::ArgAction::SetTrue)
+ .help("Find the previous prime number strictly less than the given number(s)"))
.get_matches();
env_logger::init();
info!("Welcome to Prime factorizer");
+ let is_next = args.get_flag("next");
+ let is_prev = args.get_flag("prev");
+
let numstr_vec: ValuesRef<String> = args.get_many("number").unwrap();
let mut range_vec: Vec<RangeInclusive<u128>> = Vec::new();
for numstr in numstr_vec {
@@ -43,14 +56,30 @@ fn main() {
}
}
for rng in range_vec {
- let results: Vec<_> = rng.into_par_iter().map(|n| match n {
- 0 | 1 => format!("{n} is neither prime nor composite"),
- _ => {
- let factors = PrimeFactors::factorize(n);
- if factors.is_prime() {
- format!("{n} is prime!")
- } else {
- format!("{n} = {factors}")
+ let results: Vec<_> = rng.into_par_iter().map(|n| {
+ if is_next {
+ let next_p = PrimeNumbers::from(n.saturating_add(1)).next().unwrap();
+ return format!("Next prime after {n} is {next_p}");
+ }
+ if is_prev {
+ if n <= 2 {
+ return format!("No prime strictly less than {n}");
+ }
+ let mut p = n - 1;
+ while !u128_is_prime(p) {
+ p -= 1;
+ }
+ return format!("Previous prime before {n} is {p}");
+ }
+ match n {
+ 0 | 1 => format!("{n} is neither prime nor composite"),
+ _ => {
+ let factors = PrimeFactors::factorize(n);
+ if factors.is_prime() {
+ format!("{n} is prime!")
+ } else {
+ format!("{n} = {factors}")
+ }
}
}
}).collect();
diff --git i/tests/test.rs w/tests/test.rs
index ac767e5..461ba2e 100644
--- i/tests/test.rs
+++ w/tests/test.rs
@@ -186,3 +186,19 @@ fn test_large_primes_above_mr_threshold() {
assert!(u128_is_prime(162259276829213363391578010288127)); // 2^107 - 1
assert!(u128_is_prime(170141183460469231731687303715884105727)); // 2^127 - 1
}
+
+#[test]
+fn test_benchmark_worst_cases_are_primes() {
+ // Array copied directly from `benches/benchmark.rs` FIXED_VEC
+ let primes = [
+ 13, 251, 4093, 65521, 1048573, 16777213, 268435399, 4294967291,
+ 68719476731, 1099511627689, 17592186044399, 281474976710597,
+ 4503599627370449, 72057594037927931, 1152921504606846883,
+ 18446744073709551557, 295147905179352825833, 1180591620717411303389,
+ 4722366482869645213603, 18889465931478580854749, 75557863725914323419121,
+ 302231454903657293676533, 1208925819614629174706111
+ ];
+ for p in primes {
+ assert!(primefactor::u128_is_prime(p), "Benchmark worst-case {} is not actually prime!", p);
+ }
+}