Guest User

Untitled

a guest
Apr 4th, 2021
53
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. use bitvec::prelude::*;
  2. use std::{
  3. collections::HashMap,
  4. time::{Duration, Instant},
  5. };
  6. struct PrimeCS {
  7. sieve_size: usize,
  8. bit_array: BitVec,
  9. my_dict: HashMap<usize, usize>,
  10. }
  11.  
  12. impl PrimeCS {
  13. fn generate_dictionary() -> HashMap<usize, usize> {
  14. [
  15. (10, 4),
  16. (100, 25),
  17. (1000, 168),
  18. (10000, 1229),
  19. (100000, 9592),
  20. (1000000, 78498),
  21. (10000000, 664579),
  22. (100000000, 5761455),
  23. (10000000000, 455052511),
  24. ]
  25. .iter()
  26. .copied()
  27. .collect()
  28. }
  29.  
  30. pub fn new(size: usize) -> Self {
  31. Self {
  32. sieve_size: size,
  33. bit_array: bitvec![1; size],
  34. my_dict: Self::generate_dictionary(),
  35. }
  36. }
  37. pub fn validate_results(&self) -> bool {
  38. self.my_dict
  39. .get(&self.sieve_size)
  40. .map(|n| *n == self.count_primes())
  41. .unwrap_or(false)
  42. }
  43.  
  44. pub fn run_sieve(&mut self) {
  45. let mut factor = 3;
  46. let q = f64::sqrt(self.sieve_size as f64) as usize;
  47. while factor <= q {
  48. for num in (factor..self.sieve_size).step_by(2) {
  49. match self.bit_array.get(num) {
  50. Some(b) => {
  51. if *b {
  52. factor = num;
  53. break;
  54. }
  55. }
  56. None => {}
  57. }
  58. }
  59.  
  60. for num in (factor * factor..self.sieve_size).step_by(factor * 2) {
  61. self.bit_array.get_mut(num).map(|mut b| *b = false);
  62. }
  63. factor += 2;
  64. }
  65. }
  66.  
  67. pub fn print_results(&mut self, show_results: bool, duration: Duration, passes: i32) {
  68. if show_results {
  69. print!("2, ");
  70. }
  71. let mut count = 1;
  72. for num in (3..=self.sieve_size).step_by(2) {
  73. self.bit_array.get(num).map(|v| {
  74. if *v {
  75. count += 1;
  76. if show_results {
  77. print!("{}, ", num);
  78. }
  79. }
  80. });
  81. }
  82. if show_results {
  83. println!();
  84. }
  85. println!(
  86. "Passes: {}, Time: {}, Avg: {}, Limit: {}, Count: {}, Valid: {}",
  87. passes,
  88. duration.as_secs_f32(),
  89. duration.as_secs_f32() / passes as f32,
  90. self.sieve_size,
  91. count,
  92. self.validate_results()
  93. )
  94. }
  95.  
  96. pub fn count_primes(&self) -> usize {
  97. self.bit_array
  98. .iter()
  99. .skip(3)
  100. .step_by(2)
  101. .filter(|b| **b)
  102. .count()
  103. }
  104. }
  105.  
  106. fn main() {
  107. let mut passes = 0;
  108. let t_start = Instant::now();
  109. loop {
  110. let mut sieve = PrimeCS::new(1000000);
  111. sieve.run_sieve();
  112. passes += 1;
  113. let elapsed = t_start.elapsed();
  114. if elapsed >= Duration::from_secs(5) {
  115. sieve.print_results(false, elapsed, passes);
  116. break;
  117. }
  118. }
  119. }
  120.  
RAW Paste Data