I'm fairly new to rust, and I'm converting some of my projects from Python to Rust.

This is a prime tester tool I made in python for fun (then used in some actual project)

I did multiple functions to see the improvements of various tricks to speed up (in this case) Sieve of Eratosthenes algorythm.

Until last test, rust followed the improvements I had in Python, can you help me understand what am I doing wrong?

Code is on my github too:

```
fn sieve_vanilla(n: u64) -> Vec<u64>{
let mut primes = vec![true; (n+1) as usize];
let mut res: Vec<u64> = Vec::new();
primes[0] = false;
primes[1] = false;
for i in 2..(n+1) as usize {
if primes[i] {
res.push(i as u64);
let mut j = i + i;
while j <= n as usize {
primes[j] = false;
j += i;
}
}
}
res
}
fn sieve_001(n: u64) -> Vec<u64>{
let mut primes = vec![true; (n+1) as usize];
let mut res: Vec<u64> = Vec::new();
primes[0] = false;
primes[1] = false;
for i in 2..((n+1) as f64).sqrt() as usize {
if primes[i] {
res.push(i as u64);
let mut j = i + i;
while j <= n as usize {
primes[j] = false;
j += i;
}
}
}
for i in ((n as f64).sqrt() as usize + 1)..(n+1) as usize {
if primes[i] {
res.push(i as u64);
}
}
res
}
fn sieve_002(n: u64) -> Vec<u64>{
let mut primes = vec![true; (n+1) as usize];
let mut res: Vec<u64> = Vec::new();
primes[0] = false;
primes[1] = false;
for i in 2..((n+1) as f64).sqrt() as usize {
if primes[i] {
res.push(i as u64);
let mut j = i * i;
while j <= n as usize {
primes[j] = false;
j += i;
}
}
}
for i in ((n as f64).sqrt() as usize + 1)..(n+1) as usize {
if primes[i] {
res.push(i as u64);
}
}
res
}
fn sieve_003(n: u64) -> Vec<u64>{
let mut primes: Vec<bool> = vec![[false, true]; ((n+1)/2) as usize].into_iter().flatten().collect();
if (n+1) % 2 != 0 {
primes.push(false);
}
primes[1] = false;
primes[2] = true;
let mut res: Vec<u64> = Vec::new();
res.push(2 as u64);
let limit = ((n as f64).sqrt() as usize) + 1;
for i in (3..limit).step_by(2) {
if primes[i] {
res.push(i as u64);
let mut j = i * i;
while j <= n as usize {
primes[j] = false;
j += i;
}
}
}
for i in ((n as f64).sqrt() as usize + 1)..(n+1) as usize {
if primes[i] {
res.push(i as u64);
}
}
res
}
fn _test_vec_creation(n: u64){
// test if making a true vec and loop over multiple of 2 is faster than take.flatten.collect
// method 1
let start = Instant::now();
let mut primes = vec![true; (n+1) as usize];
primes[0] = false;
primes[1] = false;
for i in (4..(n+1) as usize).step_by(2) {
primes[i] = false;
}
let duration = start.elapsed();
println!("Method 1 in {:?}", duration); // Print the elapsed time
// method 2
let start = Instant::now();
let mut primes: Vec<bool> = vec![[false, true]; ((n+1)/2) as usize].into_iter().flatten().collect();
if (n+1) % 2 != 0 {
primes.push(false);
}
primes[1] = false;
primes[2] = true;
let duration = start.elapsed();
println!("Method 2 in {:?}", duration); // Print the elapsed time
}
fn main() {
let args = Cli::parse();
if args.mode == Mode::List{
let start = Instant::now();
let _values = sieve_vanilla(args.value);
let duration = start.elapsed();
println!("sieve_vanilla Done in {:?}", duration); // Print the elapsed time
let start = Instant::now();
let _values = sieve_001(args.value);
let duration = start.elapsed();
println!("001 Done in {:?}", duration); // Print the elapsed time
let start = Instant::now();
let _values = sieve_002(args.value);
let duration = start.elapsed();
println!("002 Done in {:?}", duration); // Print the elapsed time
let start = Instant::now();
let _values = sieve_003(args.value);
let duration = start.elapsed();
println!("003 Done in {:?}", duration); // Print the elapsed time
}
}
```

With 25milion as input I have:

```
sieve_vanilla Done in 807.8685ms
001 Done in 643.6626ms
002 Done in 611.4306ms
003 Done in 991.5997ms
```

The 003 is slower than 002, when essentially I improved a lot of things there:

- My Vec of primes generation is halved thanks to

`vec![[false, true]; ((n+1)/2) as usize].into_iter().flatten().collect();`

- The foor loop starts at 3 and has step of 2, halvening the value to check

Point 1 is correct in Python but it is essentially slower in rust! The function

```
fn _test_vec_creation(n: u64){
// test if making a true vec and loop over multiple of 2 is faster than take.flatten.collect
// method 1
let start = Instant::now();
let mut primes = vec![true; (n+1) as usize];
primes[0] = false;
primes[1] = false;
for i in (4..(n+1) as usize).step_by(2) {
primes[i] = false;
}
let duration = start.elapsed();
println!("Method 1 in {:?}", duration); // Print the elapsed time
// method 2
let start = Instant::now();
let mut primes: Vec<bool> = vec![[false, true]; ((n+1)/2) as usize].into_iter().flatten().collect();
if (n+1) % 2 != 0 {
primes.push(false);
}
primes[1] = false;
primes[2] = true;
let duration = start.elapsed();
println!("Method 2 in {:?}", duration); // Print the elapsed time
}
```

Serve just this purpose to test the two Vec creation methods, with n = 25milion the results:

```
Method 1 in 172.89ms
Method 2 in 553.5054ms
```

Instead in python the improvement in method 3 was awesome:

```
Vanilla: 0.21936464309692383
1: 0.11927986145019531
2: 0.10861492156982422
3: 0.0701291561126709
```

Can you help me understand if it just different in Rust or if my flatten implementation is slowing everything and there is a *Rustic* way of doing it?

Thanks