Counting primes less than n The following code was written to be a submission to this challenge on PPCG. 

It uses this algorithm, the Meissal-Lehmer method. I follow the Wikipedia entry pretty naively, except I tried to memoize the phi function.

Please see @Shepmaster's answer for cleaned up, more idiomatic Rust.

I am looking for ways to improve speed. Most improvements I believe will come from optimizing the phi function, which is used recursively. Answers about making my code more idiomatic Rust are also welcome. 

I've been compiling with cargo build --release. The code runs in ~3 sec for input 1,000,000 and a lot longer for 10,000,000.

use std::env;

fn main() {
    let args: Vec&lt;_&gt; = env::args().collect();
    let x: usize = (args[1]).trim().parse()
        .expect("expected a number");





    let root: usize = (x as f64).sqrt() as usize;
    let y: usize = (x as f64).powf(0.3333333333333) as usize + 1;

    let sieve_size: usize = x/y+2;//y+1;
    let mut sieve: Vec&lt;bool&gt; = vec![true; sieve_size ];
    let mut primes: Vec&lt;usize&gt; = vec![0; sieve_size ];
    sieve[0] = false; sieve[1] = false;


    let mut a: usize = 0;
    let mut num_primes = 1;

    let mut num_primes_smaller_root: usize = 0;

    // find all primes up to x/y ~ x^2/3 aka sieve_size
    for i in 2..sieve_size {
        if sieve[i] {
            if i&lt;= root {
                if i&lt;=y {
                    a+=1;
                }
                num_primes_smaller_root+=1;
            }


            primes[num_primes] = i;
            num_primes +=1;
            let mut multiples: usize = i;
            while multiples &lt; sieve_size {
                sieve[multiples] = false;
                multiples += i;
            }
        }
    }



    let mut phi_results: Vec&lt;Vec&lt;usize&gt;&gt; = vec![ vec![0; a+1 ];x+1 ];



    let mut p_2: usize = 0;
    for i in a+1..num_primes_smaller_root+1 {
        let mut first_term: usize = 0;
        while primes[first_term]&lt; x/primes[i] {
            //println!("checking {} vs {}...",primes[first_term],x/primes[i]);
            first_term+=1;
        }
        if primes[first_term]==x/primes[i] {
            first_term +=1;
        }
        p_2 += (first_term -1) - i + 1;
    }

    /*println!("y={}; a={}",y,a);
    println!("P2 = {}",p_2);
    println!("phi({},{}) = {}",x, a, phi(x,a,&amp;primes));
    */ 
    println!("pi({}) = {}", x, phi(x,a,&amp;primes,&amp;mut phi_results)+a-1-p_2);
}

fn phi(x:usize, b:usize, primes:&amp;Vec&lt;usize&gt;, phi_results:&amp;mut Vec&lt;Vec&lt;usize&gt;&gt;)-&gt;usize {
    if b==0 {
        return x;
    }
    if phi_results[x][b] != 0 {
        return phi_results[x][b];
    }
    let value: usize = phi(x,b-1,primes,phi_results) - phi(x/primes[b],b-1,primes,phi_results);
    phi_results[x][b] = value;
    return value;
}


I'm kind of new to the site, so please let me know how to improve this post as a whole too, if necessary
Here's my first pass on stylistic feedback.


Unneeded parenthesis around args[1]
Redundant type specifications, everywhere
Remove commented-out code
Add spaces around binary operators (/, +, &lt;=, +=)
Don't have double semicolons at the end of the line
Don't add space inside [], like in vec![]
Split multiple statements on different lines
Add spaces after commas
Add spaces after colons
Basically never use &amp;Vec&lt;T&gt;, use &amp;[T] instead
Don't use an explicit return at the end of function
Typo in the println! (pi vs phi)


I believe that you can change some of the loops to use more iterators, but I haven't figured those out yet.



use std::env;

fn main() {
    let args: Vec&lt;_&gt; = env::args().collect();
    let x: usize = args[1].trim().parse().expect("expected a number");

    let root = (x as f64).sqrt() as usize;
    let y = (x as f64).powf(0.3333333333333) as usize + 1;

    let sieve_size = x / y + 2;
    let mut sieve = vec![true; sieve_size];
    let mut primes = vec![0; sieve_size];
    sieve[0] = false;
    sieve[1] = false;

    let mut a = 0;
    let mut num_primes = 1;

    let mut num_primes_smaller_root = 0;

    // find all primes up to x/y ~ x^2/3 aka sieve_size
    for i in 2..sieve_size {
        if sieve[i] {
            if i &lt;= root {
                if i &lt;= y {
                    a += 1;
                }
                num_primes_smaller_root += 1;
            }

            primes[num_primes] = i;
            num_primes += 1;
            let mut multiples = i;
            while multiples &lt; sieve_size {
                sieve[multiples] = false;
                multiples += i;
            }
        }
    }

    let mut phi_results = vec![vec![0; a + 1]; x + 1];

    let mut p_2 = 0;
    for i in a + 1..num_primes_smaller_root + 1 {
        let mut first_term = 0;
        while primes[first_term] &lt; x / primes[i] {
            first_term += 1;
        }
        if primes[first_term] == x / primes[i] {
            first_term += 1;
        }
        p_2 += (first_term - 1) - i + 1;
    }

    println!("pi({}) = {}", x, phi(x, a, &amp;primes, &amp;mut phi_results) + a - 1 - p_2);
}

fn phi(x: usize, b: usize, primes: &amp;[usize], phi_results: &amp;mut [Vec&lt;usize&gt;]) -&gt; usize {
    if b == 0 {
        return x;
    }

    if phi_results[x][b] != 0 {
        return phi_results[x][b];
    }

    let value = phi(x, b - 1, primes, phi_results) - phi(x / primes[b], b - 1, primes, phi_results);
    phi_results[x][b] = value;
    value
}




When I run this code with 1000000 it takes ~300 milliseconds:

$ cargo build --release &amp;&amp; time ./target/release/sieve 1000000
phi(1000000) = 78498

real    0m0.307s
user    0m0.204s
sys     0m0.102s


Note that you need to build the code and time it in a separate pass, to not include the time spent compiling.



Performance-wise, I'm not seeing many obvious changes.


Try to avoid direct slice access when feasible (vector[0]). These accesses are checked at run time to avoid walking off into undefined memory. Iterators guarantee that no undefined memory will be accessed and can sidestep that small performance bit.


Iterator adapters can also allow removing mutability:

let mut p_2 = 0;
for (i, zz) in primes[a + 1..num_primes_smaller_root + 1].iter().enumerate() {
    let i = i + a + 1;
    let first_term = primes.iter().take_while(|&amp;&amp;p| p &lt;= x / zz).count();
    p_2 += (first_term - 1) - i + 1;
}


Then, move that arithmetic on i to the end, and apply more adapters to remove more mutability:

let interesting_primes = primes[a + 1..num_primes_smaller_root + 1].iter();

let p_2 =
    interesting_primes
    .map(|ip| primes.iter().take_while(|&amp;&amp;p| p &lt;= x / ip).count())
    .enumerate()
    .map(|(i, v)| v - 1 - i - a)
    .fold(0, |acc, v| acc + v);