prime_formula/
lib.rs

1//! A high-performance prime number generator implementing a novel prime formula.
2//!
3//! This library enables efficient finding of prime numbers and prime constellations
4//! (twin primes, triplets, etc.) using The Periodic Table of Primes which is a novel
5//! theory that claims that all primes are descendants of just 48 Prime Roots, and that
6//! these descendants are in the form root + k×210.
7//!
8//! The implementation leverages:
9//! - Bitwise storage for compact representation
10//! - Rayon-based parallelism for multi-core scaling
11//! - Three distinct search modes optimized for different number ranges
12//!
13//! The core algorithm operates by eliminating composite candidates using precomputed
14//! prime root relationships rather than checking every potential divisor. The library
15//! implements theory proposed by Han-Lin Li, Shu-Cherng Fang & Way Kuo.
16//!
17//! For more info, see <https://ssrn.com/abstract=4742238>
18//
19// Copyright: Adam Cottrell (cottrela@gmail.com)
20
21// use bitvec::prelude::*;
22use rayon::prelude::*;
23use rayon::slice::ParallelSliceMut;
24
25use crate::common::{ConfigMode, NUM_ROOTS, get_small_primes};
26use crate::prime::{PrimalityTest, PrimeFormula};
27use crate::sieve::{Sieve, SieveMode};
28
29pub mod common;
30
31// Adds support for quickly finding many smaller primes
32pub mod sieve;
33
34// Adds support for quickly finding constellations of primes
35#[cfg(feature = "constellations")]
36pub mod constellations;
37
38// Adds support for quickly finding large primes
39pub mod prime;
40
41// Adds support for quickly finding one or more huge primes
42#[cfg(feature = "big-primes")]
43pub mod big_prime;
44
45/// Parallel prime number generator for a range
46///
47/// Uses all available CPU cores to process different prime roots simultaneously
48///
49/// # Arguments
50/// - start: Inclusive lower bound
51/// - end: Exclusive upper bound
52/// - mode: Sieve strategy selection
53pub fn get_primes(start: u128, end: u128, mode: &ConfigMode) -> Vec<u128> {
54    let mut primes: Vec<u128>;
55    if *mode == ConfigMode::MillerRabinDeterministic {
56        let inst = PrimeFormula::new(PrimalityTest::MillerRabinDeterministic, 8);
57        primes = inst.get_unsorted_primes(start, end);
58    } else if *mode == ConfigMode::MillerRabinProbabilistic {
59        let inst = PrimeFormula::new(PrimalityTest::MillerRabinProbabilistic, 8);
60        primes = inst.get_unsorted_primes(start, end);
61    } else {
62        primes = (0..NUM_ROOTS)
63            .into_par_iter()
64            .flat_map(
65                |root_idx| match Sieve::new(root_idx as u8, start, end, SieveMode::Sieve) {
66                    Ok(mut sieve) => sieve.get_primes(),
67                    Err(_e) => vec![0; 0],
68                },
69            )
70            .collect();
71    }
72
73    // Add small primes, if necessary
74    primes.extend(get_small_primes(start, end));
75
76    // Primes arrive interleaved, and so must be resorted
77    primes.par_sort_unstable();
78
79    primes
80}
81
82/// Parallel prime counter for a range
83///
84/// More memory-efficient than get_primes() as it doesn't store results
85pub fn count_primes(start: u128, end: u128, mode: &ConfigMode) -> usize {
86    let mut count: usize = get_small_primes(start, end).len();
87    count += if *mode == ConfigMode::MillerRabinDeterministic {
88        let inst = PrimeFormula::new(PrimalityTest::MillerRabinDeterministic, 8);
89        let primes = inst.get_unsorted_primes(start, end);
90        primes.len()
91    } else if *mode == ConfigMode::MillerRabinProbabilistic {
92        let inst = PrimeFormula::new(PrimalityTest::MillerRabinProbabilistic, 8);
93        let primes = inst.get_unsorted_primes(start, end);
94        primes.len()
95    } else {
96        (0..NUM_ROOTS)
97            .into_par_iter()
98            .map(
99                |root_idx| match Sieve::new(root_idx as u8, start, end, SieveMode::Sieve) {
100                    Ok(mut sieve) => sieve.count_primes(),
101                    Err(_e) => 0,
102                },
103            )
104            .sum()
105    };
106
107    count
108}
prime_formula/lib.rs

prime_formula/
lib.rs
