fork download
copy 
  1. use std::io;
  2.  
  3. // from
  4. // stackoverflow.com/questions/73682463/
  5. // my-prime-number-sieve-is-extremely-slow-even-with-release
  6.  
  7. // edited by stackoverflow.com/users/849891/will-ness
  8.  
  9. pub fn number_to_vector(number: i32) -> Vec<i32> {
  10.     let mut numbers: Vec<i32> = Vec::new();
  11.  
  12.     for i in 1..number + 1 {
  13.         numbers.push(i);
  14.     }
  15.  
  16.     return numbers;
  17. }
  18.  
  19.  
  20. pub fn get_user_input(prompt: &str) -> i32 {
  21.     println!("{}", prompt);
  22.  
  23.     let mut user_input: String = String::new();
  24.  
  25.     io::stdin().read_line(&mut user_input).expect("Failed to read line");
  26.  
  27.     let number: i32 = user_input.trim().parse().expect("Please enter an integer!");
  28.  
  29.     return number;
  30. }
  31.  
  32.  
  33. fn main() {
  34.     let user_input: i32 = get_user_input("Enter a positive integer: ");
  35.     let mut numbers: Vec<i32> = number_to_vector(user_input);
  36.     numbers.remove(numbers.iter().position(|x| *x == 1).unwrap());
  37.     let mut numbers_to_remove: Vec<i32> = Vec::new();
  38.     let mut primes: Vec<i32> = Vec::new();
  39.     let mut i = 0;
  40.  
  41.     let ceiling_root: i32 = (user_input as f64).sqrt().ceil() as i32;
  42.  
  43.     for i in 2..ceiling_root + 1 {
  44.         for j in i..(user_input/i) + 1 {
  45.             numbers_to_remove.push(i * j);
  46.         }
  47.     }
  48.  
  49.     numbers_to_remove.sort_unstable();
  50.     numbers_to_remove.dedup();
  51.     //numbers_to_remove.retain(|x| *x <= user_input);
  52.  
  53.     /* for n in numbers_to_remove {
  54.         if numbers.iter().any(|&i| i == n) {
  55.             numbers.remove(numbers.iter().position(|x| *x == n).unwrap());
  56.         }
  57.     } */
  58.  
  59.     for n in numbers {
  60.     	if n < numbers_to_remove[i] {
  61.     		primes.push(n);
  62.     	}
  63.     	else {
  64.     		i += 1;
  65.     	}
  66.     }
  67.  
  68.     //println!("Prime numbers up to {}: {:?}", user_input, numbers);
  69.  
  70.     println!("Last prime number up to {}: {:?}", user_input, primes.last());
  71.     println!("Total prime numbers up to {}: {:?}", user_input, 
  72.          primes.iter().count());
  73. }
  74.  
  75.  
Success #stdin #stdout 0.28s 31548KB
comments (?)
stdin
copy 
1000000

1M  0.26s 32048KB
2M  0.54s 60084KB  n^1.05

Last prime number up to 1000000: Some(999983)
Total prime numbers up to 1000000: 78498

Last prime number up to 2000000: Some(1999993)
Total prime numbers up to 2000000: 148933
stdout
copy 
Enter a positive integer: 
Last prime number up to 1000000: Some(999983)
Total prime numbers up to 1000000: 78498
https://ideone.com/p2sxGl
language:
Rust (rust 1.56)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!