1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146

//! Primeval-rs
//!
//!A monstrosity of a prime number generator. (It's dead simple)
//!
//!## Features

//!- ZERO Dependencies (will always be this way)
//!- CLI Interface
//!- Rust library (see [crates.io](https://crates.io/crates/primeval))
//!
//!## Usage
//!
//!### CLI
//!
//!- `primeval help`: displays a help menu.
//!- `primeval gen <limit>`: generates all the prime numbers up to a limit
//!- `primeval prime <number>`: determines whether a number is prime or not
//!- `primeval version`: shows version info
//!
//!### Rust Crate
//!
//!*main.rs*
//!```rust
//!extern crate primeval;
//!
//!fn main(){
//!  // Primality?
//!  let result = primeval::is_prime(2);
//!
//!  // Generation, in this case all the primes from 0 - 1000
//!  let result: Vec<usize> = primeval::primes_gen(1000).collect::<Vec<_>>();
//!}
//!```
//!
//!## Installation (CLI)
//!
//!1. `git clone https://github.com/ajmwagar/primeval-rs`
//!2. `cd primeval-rs`
//!3. `cargo build --release`
//!4. `cd target/release`
//!5. `./primeval help`
//!6. Profit!
//!
//!You can also move the binary into `/usr/bin` or somewhere else in your `PATH` to use from anywhere.
//!
//!## Tests & Benchmarks
//!
//!- To run the test suite: `cargo test`
//!- Always looking for more! (Submit a pull request)
//!- To benchmark Primeval: `cargo bench`
//!- Benchmarks prime number generation up to 1000000
//!
//!## Roadmap
//!
//!- [x] Rust Module/API
//!- [ ] Cleaner UI/CLI
//!- [ ] More SPEED!
//!- [ ] Factorization
//!- [ ] Larger number support
//!- [ ] Heat death of the universe

use std::*;
use std::iter;

/// Returns whether a given number is prime
pub fn is_prime(n: usize) -> bool {
    if n > 1 {
        if n >=  8 {
            // Get list of primes
            let primes = &primes_gen(n.clone() + 1).collect::<Vec<_>>();

            // Check if n is prime
            for &p in primes {
                let q: usize = n / p as usize;
                if q < p as usize { return true };
                let r = n - q * p as usize;
                if r == 0 { return false };
            }

            panic!("too few primes")
        }
        else {
            let primes = vec![2, 3, 5, 7];

            return primes.contains(&n);
        }
    }
    else {
        return false;
    }
}

/// Generate primes up to a given limit using the Seive of Eratorthenes
/// Use Sieve_of_Eratosthenes for prime generation (https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes)
pub fn primes_gen(limit: usize) -> Box<dyn Iterator<Item = usize>> {
    if limit >= 10 {


    // Automatically return the small primes
    if limit < 3 {
        return if limit < 2 { Box::new(iter::empty::<usize>()) } else { Box::new(iter::once(2)) }
    }

    // Setup the indexs
    let indexlimit = (limit - 3) / 2 + 1;
    let buffersize = ((limit - 3) / 2) / 32 + 1;
    let mut composites = vec![0u32; buffersize];
    let sqrtindexlimit = ((limit as f64).sqrt() as usize - 3) / 2 + 1;

    // Go through the 0-sqrtindexlimit
    for index in 0..sqrtindexlimit {
        if (composites[index >> 5] & (1u32 << (index & 31))) == 0 {
            let p = index + index + 3;
            let mut cullpos = (p * p - 3) / 2;
            // Cull through the composites
            while cullpos < indexlimit {
                unsafe {
                    // avoids array bounds check, which is already done above
                    let cptr = composites.get_unchecked_mut(cullpos >> 5);
                    *cptr |= 1u32 << (cullpos & 31);
                }
                cullpos += p;
            }
        }
    }

    Box::new((-1 .. indexlimit as isize).into_iter().filter_map(move |i| {
        if i < 0 { 
            // Set initial prime
            Some(2)
        } 
        else {
            if composites[i as usize >> 5] & (1u32 << (i & 31)) == 0 {
                // Add this value to the box
                Some((i + i + 3) as usize) 
            } else { 
                // Dont add this value
                None 
            }
        }
    }))
    }
    else {
        return Box::new(vec![2,3,5,7].into_iter().filter(move |x| x <= &limit));
    }
}