质数筛法

  1. pub fn prime_numbers(max: usize) -> Vec<usize> {
  2.     let mut result: Vec<usize> = Vec::new();
  4.     if max >= 2 {
  5.         result.push(2)
  6.     }
  7.     for i in (3..max + 1).step_by(2) {
  8.         let stop: usize = (i as f64).sqrt() as usize + 1;
  9.         let mut status: bool = true;
  11.         for j in (3..stop).step_by(2) {
  12.             if i % j == 0 {
  13.                 status = false
  14.             }
  15.         }
  16.         if status {
  17.             result.push(i)
  18.         }
  19.     }
  21.     result
  22. }
  24. #[cfg(test)]
  25. mod tests {
  26.     use super::*;
  28.     #[test]
  29.     fn basic() {
  30.         assert_eq!(prime_numbers(0), vec![]);
  31.         assert_eq!(prime_numbers(11), vec![2, 3, 5, 7, 11]);
  32.         assert_eq!(prime_numbers(25), vec![2, 3, 5, 7, 11, 13, 17, 19, 23]);
  33.         assert_eq!(
  34.             prime_numbers(33),
  35.             vec![2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]
  36.         );
  37.     }
  38. }