prime-formula 0.3.1

//! A high-performance prime number generator implementing a novel prime formula.
//!
//! This library enables efficient finding of prime numbers and prime constellations
//! (twin primes, triplets, etc.) using The Periodic Table of Primes which is a novel
//! theory that claims that all primes are descendants of just 48 Prime Roots, and that
//! these descendants are in the form root + k×210.
//!
//! The implementation leverages:
//! - Bitwise storage for compact representation
//! - Rayon-based parallelism for multi-core scaling
//! - Three distinct search modes optimized for different number ranges
//!
//! The core algorithm operates by eliminating composite candidates using precomputed
//! prime root relationships rather than checking every potential divisor. The library
//! implements theory proposed by Han-Lin Li, Shu-Cherng Fang & Way Kuo.
//!
//! For more info, see <https://ssrn.com/abstract=4742238>
//
// Copyright: Adam Cottrell (cottrela@gmail.com)

// use bitvec::prelude::*;
use rayon::prelude::*;
use rayon::slice::ParallelSliceMut;

use crate::common::{ConfigMode, NUM_ROOTS, get_small_primes};
use crate::prime::{PrimalityTest, PrimeFormula};
use crate::sieve::{Sieve, SieveMode};

pub mod common;

// Adds support for quickly finding many smaller primes
pub mod sieve;

// Adds support for quickly finding constellations of primes
#[cfg(feature = "constellations")]
pub mod constellations;

// Adds support for quickly finding large primes
pub mod prime;

// Adds support for quickly finding one or more huge primes
#[cfg(feature = "big-primes")]
pub mod big_prime;

/// Parallel prime number generator for a range
///
/// Uses all available CPU cores to process different prime roots simultaneously
///
/// # Arguments
/// - start: Inclusive lower bound
/// - end: Exclusive upper bound
/// - mode: Sieve strategy selection
pub fn get_primes(start: u128, end: u128, mode: &ConfigMode) -> Vec<u128> {
    let mut primes: Vec<u128>;
    if *mode == ConfigMode::MillerRabinDeterministic {
        let inst = PrimeFormula::new(PrimalityTest::MillerRabinDeterministic, 8);
        primes = inst.get_unsorted_primes(start, end);
    } else if *mode == ConfigMode::MillerRabinProbabilistic {
        let inst = PrimeFormula::new(PrimalityTest::MillerRabinProbabilistic, 8);
        primes = inst.get_unsorted_primes(start, end);
    } else {
        primes = (0..NUM_ROOTS)
            .into_par_iter()
            .flat_map(
                |root_idx| match Sieve::new(root_idx as u8, start, end, SieveMode::Sieve) {
                    Ok(mut sieve) => sieve.get_primes(),
                    Err(_e) => vec![0; 0],
                },
            )
            .collect();
    }

    // Add small primes, if necessary
    primes.extend(get_small_primes(start, end));

    // Primes arrive interleaved, and so must be resorted
    primes.par_sort_unstable();

    primes
}

/// Parallel prime counter for a range
///
/// More memory-efficient than get_primes() as it doesn't store results
pub fn count_primes(start: u128, end: u128, mode: &ConfigMode) -> usize {
    let mut count: usize = get_small_primes(start, end).len();
    count += if *mode == ConfigMode::MillerRabinDeterministic {
        let inst = PrimeFormula::new(PrimalityTest::MillerRabinDeterministic, 8);
        let primes = inst.get_unsorted_primes(start, end);
        primes.len()
    } else if *mode == ConfigMode::MillerRabinProbabilistic {
        let inst = PrimeFormula::new(PrimalityTest::MillerRabinProbabilistic, 8);
        let primes = inst.get_unsorted_primes(start, end);
        primes.len()
    } else {
        (0..NUM_ROOTS)
            .into_par_iter()
            .map(
                |root_idx| match Sieve::new(root_idx as u8, start, end, SieveMode::Sieve) {
                    Ok(mut sieve) => sieve.count_primes(),
                    Err(_e) => 0,
                },
            )
            .sum()
    };

    count
}