Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /* author Bill Wood */
- fn sqrt(n: usize) -> usize {
- let (mut r1, mut r) = (n, n + 1);
- while r1 < r {
- r = r1;
- r1 = (r1 + n/r1) >> 1
- }
- r
- }
- struct SimpleSieve {
- primes: Vec<u32>,
- }
- impl SimpleSieve {
- fn new(high: usize) -> Self {
- assert_eq!(high | 1, high);
- let mut pvec = vec![false; (high + 1)/2];
- let mut primes = vec![];
- let n = high >> 1;
- let mut i = 3;
- while i*i <= high {
- if !pvec[i >> 1] {
- primes.push(i as u32);
- let mut j = (i*i) >> 1;
- while j <= n {
- pvec[j] = true;
- j += i;
- }
- }
- i += 2;
- }
- i >>= 1;
- while i <= n {
- if !pvec[i] {
- primes.push(((i << 1) | 1) as u32);
- }
- i += 1;
- }
- dbg!(primes.len());
- SimpleSieve { primes, }
- }
- }
- type CBFn<'a> = &'a mut dyn FnMut(usize);
- struct SieveSlice<'a> {
- low: usize,
- high: usize,
- bslice: &'a mut [bool],
- }
- impl<'a> SieveSlice<'a> {
- fn new(low: usize, high: usize, bslice: &'a mut [bool]) -> Self {
- // assert_eq!(low | 1, low);
- // assert_eq!(high | 1, high);
- // dbg!(low, high, );
- SieveSlice { low, high, bslice }
- }
- fn find(&mut self, f: CBFn, sieve: &SimpleSieve) {
- let (low, high) = (self.low, self.high);
- // generate primes
- let n = (high + 2 - low) >> 1;
- for i in 0..sieve.primes.len() {
- let p = sieve.primes[i] as usize;
- let mut j = p*p;
- if j < low {
- j += (low - 1 - j + p*2)/2/p*p*2;
- }
- if j > high {//?? moved here
- break;
- }
- j = (j - low) >> 1;
- while j < n {
- self.bslice[j] = true;
- j += p;
- }
- }
- // callback primes
- if low < 2 && high > 2 {
- self.bslice[0] = true; // 1 is not prime
- f(2); // 2 is prime
- }
- for i in 0..n {
- if !self.bslice[i] {
- f((i << 1) + low);
- }
- }
- }
- }
- use rayon::prelude::*;
- struct Primes {
- low: usize,
- high: usize,
- seg_size: usize,
- seg_num_chunks: usize,
- }
- impl Primes {
- fn new(mut low: usize, mut high: usize, seg_size_kb: usize, seg_num_chunks: usize) -> Result<Self, ()> {
- // lowest odd >= low
- low |= 1;
- if low > high || seg_size_kb == 0 || seg_num_chunks == 0 || seg_size_kb*1024 < seg_num_chunks {
- return Err(());
- }
- // highest odd <= high
- high = (high - 1) | 1;
- let seg_size = seg_size_kb.next_power_of_two()*1024;
- Ok(Primes { low, high, seg_size, seg_num_chunks })
- }
- fn callback(&self, f: CBFn) {
- let high = self.high;
- // x where x: odd and (x+2)^2 > high and x^2 < high
- let ss_high = (sqrt(high) - 1) | 1;
- let sieve = SimpleSieve::new(ss_high);
- // track odds only
- let seg_nprimes_per_byte = 2;
- let mut seg_low = self.low;
- dbg!(self.low, ss_high, seg_low, high, self.seg_num_chunks, self.seg_size, );
- let mut sieve_seg = vec![false; self.seg_size];
- let mut c = 0;
- while seg_low <= high {
- let mut segments = vec!();
- for bslice in sieve_seg.chunks_mut(self.seg_size/self.seg_num_chunks) {
- let mut seg_high = seg_low + bslice.len()*seg_nprimes_per_byte - 2;
- if seg_high > high {
- seg_high = high;
- }
- segments.push(SieveSlice::new(seg_low, seg_high, bslice));
- seg_low = seg_high + 2;
- if seg_low > high {
- break;
- }
- }
- //dbg!(segments[0].bslice.len(), segments.len());
- segments.iter_mut().for_each(|seg| seg.find(f, &sieve));
- sieve_seg.iter_mut().for_each(|x| *x = false);
- c += 1;
- }
- dbg!(c);
- }
- }
- #[derive(Debug)]
- struct FILO<T>(Vec<T>);
- impl<T: Copy + PartialEq> FILO<T> {
- fn new(value: T, size: usize) -> Self {
- FILO(vec![value; size])
- }
- #[inline(always)]
- fn push(&mut self, mut value: T) -> T {
- self.0.iter_mut().for_each(|v| { let tmp = *v; *v = value; value = tmp; } );
- self.0[self.0.len() - 1]
- }
- #[inline(always)]
- fn contains(&self, value: T) -> bool {
- self.0.iter().any(|x| *x == value)
- }
- }
- use time::PreciseTime;
- use std::io::Write;
- fn main() {
- let mut args = std::env::args()
- .skip(1)
- .map(|a| a
- .split('_')
- .fold("".to_string(), |a, s| a + s)
- .parse::<usize>());
- if args.len() <= 4 {
- if let (Ok(low), Ok(high), Ok(seg_size_kb), Ok(seg_num_chunks)) = (
- args.next().unwrap_or(Ok(3)),
- args.next().unwrap_or(Ok(1000000)),
- args.next().unwrap_or(Ok(32)),
- args.next().unwrap_or(Ok(4))) {
- let start = PreciseTime::now();
- if let Ok(primes) = Primes::new(low, high + 6, seg_size_kb, seg_num_chunks) {
- let mut count = 0;
- let mut nprimes = 0;
- let mut pbuf = FILO::new(0, 3);
- primes.callback(&mut |p| {//?? &mut? dyn?
- if p <= high {
- nprimes += 1;
- if p < 200 { print!("{} ", p); }
- }
- if pbuf.contains(p) {
- count += 1;
- }
- pbuf.push(p + 6);
- });
- let end = PreciseTime::now();
- println!("\ndone counting primes in {:.2} secs...", start.to(end).num_milliseconds() as f64 / 1000.0);
- println!("{} of {} primes are sexy", count, nprimes);
- return;
- }
- }
- }
- writeln!(
- std::io::stderr(),
- "Usage: sexy_primes low high seg_size(kb)"
- ).unwrap();
- std::process::exit(1);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement