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 Bvec {
- v: Vec<u8>
- }
- impl Bvec {
- fn new(val: bool, s: usize) -> Self {
- let valu8 = if val { 255 } else { 0 };
- Bvec { v: vec![valu8; (s >> 3) + if (s & 7) == 0 { 0 } else { 1 } ] }
- }
- #[inline(always)]
- fn get(&self, index: usize) -> bool {
- self.v[index >> 3] & 1 << (index & 7) != 0
- }
- #[inline(always)]
- fn set(&mut self, mut index: usize, val: bool) {
- let bitpos = 1 << (index & 7);
- index >>= 3;
- if val {
- self.v[index] |= bitpos;
- } else {
- self.v[index] &= !bitpos;
- }
- }
- }
- fn simple_sieve(mut high: usize) -> Vec<u32> {
- // x where x: odd and (x+2)^2 > high and x^2 < high
- high = (sqrt(high) - 1) | 1;
- 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;
- }
- primes
- }
- use rayon::prelude::*;
- 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() <= 3 {
- if let (Ok(mut low), Ok(mut high), Ok(seg_size_kb), ) = (
- args.next().unwrap_or(Ok(1_000_000_000)),
- args.next().unwrap_or(Ok(2_000_000_000)),
- args.next().unwrap_or(Ok(128)),) {
- println!("S14: Finding sexy primes with args {} {} {}", low, high, seg_size_kb, );
- let start = PreciseTime::now();
- low = low | 1; // lowest odd >= low
- if low < 3 {
- low = 3;
- }
- high = (high - 1) | 1; // highest odd <= high
- // prepare for parallel segment sieve
- let primes_per_seg = seg_size_kb.next_power_of_two()*1024*8*2;
- let mut seg_low = low;
- let mut segs = vec![];
- while seg_low < high {
- let mut seg_high = seg_low + primes_per_seg - 2;
- if seg_high > high {
- seg_high = high;
- }
- segs.push((seg_low, seg_high + 6));
- seg_low = seg_high + 2;
- }
- // get sieving primes
- let sieve_primes = simple_sieve(high);
- // find sexy primes
- let (sexy_count, nprimes) =
- segs.into_par_iter()
- .map(|(low, high)| {
- let n = (high + 2 - low) >> 1;
- let mut sieve_seg = Bvec::new(false, n);
- for i in 0..sieve_primes.len() {
- let p = sieve_primes[i] as usize;
- let mut j = p*p;
- if j > high {
- break;
- }
- if j < low {
- j += (low - 1 - j + p*2)/2/p*p*2;
- }
- j = (j - low) >> 1;
- while j < n {
- sieve_seg.set(j, true);
- j += p;
- }
- }
- let (mut sexy_count, mut nprimes) = (0_usize, 0_usize);
- for i in 0..n - 6/2 {
- if !sieve_seg.get(i) {
- nprimes += 1;
- if !sieve_seg.get(i + 6/2) {
- sexy_count += 1;
- }
- }
- }
- (sexy_count, nprimes)
- })
- .reduce(|| (0, 0),
- |a, b| (a.0 + b.0, a.1 + b.1));
- let end = PreciseTime::now();
- println!("done generating primes in {:.2} secs...", start.to(end).num_milliseconds() as f64 / 1000.0);
- println!("\n{} of {} primes are sexy", 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