sieve

Full source code

C++

#include <iostream>
#include <vector>
#include <list>
#include <cstdlib>

using namespace std;

void sieve(list<int>& unknown, vector<int>& primes)
{
  while (!unknown.empty())
  {
    int p = unknown.front();
    unknown.pop_front();
    list<int>::iterator i = unknown.begin();
    while (i != unknown.end())
    {
      if (*i % p)
        ++i;
      else
        i = unknown.erase(i);
    }
    primes.push_back(p);
  }
}

int main(int argc, char *argv[]) 
{
#ifdef SMALL_PROBLEM_SIZE
#define LENGTH 50
#else
#define LENGTH 500
#endif
  size_t NUM = (argc == 2 ? (atoi(argv[1]) < 1 ? 1 : atoi(argv[1])): LENGTH);

  vector<int> primes;

  // run the sieve repeatedly
  while (NUM--) {
    list<int> integers;
    for (int i = 2; i < 8192; ++i)
      integers.push_back(i);
    primes.clear();
    sieve(integers, primes);
  }

  cout << "Count: " << primes.size() << endl;
  return 0;
}

Rust

// Adapted from https://github.com/llvm/llvm-test-suite and
// http://www.bagley.org/~doug/shootout/
use std::env;

// Use VecDeque instead of LinkedList because Rust doesn't have stable
// ways to remove items from LinkedList and strongly encourage using
// Vec or VecDeque.
use std::collections::VecDeque;

#[cfg(feature = "small_problem_size")]
const LENGTH: i32 = 50;

#[cfg(not(feature = "small_problem_size"))]
const LENGTH: i32 = 500;

fn sieve(unknown: &mut VecDeque::<i32>, primes: &mut Vec::<i32>) {
    while unknown.len() > 0 {
        let p = unknown.pop_front().unwrap();
        unknown.retain(|&x| x % p != 0);
        primes.push(p);
    }
}

fn main() {
    let mut args = env::args();
    let mut num = if args.len() == 2 {
        let arg1 = args.nth(1).unwrap().parse::<i32>().unwrap();
        if arg1 < 1 { 1 } else { arg1 }
    } else {
        LENGTH
    };
    let mut primes = Vec::<i32>::new();

    // run the sieve repeatedly
    while num != 0 {
        let mut integers = VecDeque::<i32>::new();
        for i in 2..8192 {
            integers.push_back(i);
        }
        primes.clear();
        sieve(&mut integers, &mut primes);
        num -= 1;
    }

    println!("Count: {}", primes.len());
}

Porting notes

Using VecDeque instead of LinkedList

C++

void sieve(list<int>& unknown, vector<int>& primes)
{
  while (!unknown.empty())
  {
    int p = unknown.front();
    unknown.pop_front();
    list<int>::iterator i = unknown.begin();
    while (i != unknown.end())
    {
      if (*i % p)
        ++i;
      else
        i = unknown.erase(i);
    }
    primes.push_back(p);
  }
}

Rust

#![allow(unused)]
fn main() {
fn sieve(unknown: &mut VecDeque::<i32>, primes: &mut Vec::<i32>) {
    while unknown.len() > 0 {
        let p = unknown.pop_front().unwrap();
        unknown.retain(|&x| x % p != 0);
        primes.push(p);
    }
}
}

The Rust LinkedList interestingly does not support mutation such as element insertion and removal in its stable API, as of this writing. Rust instead encourages to use VecDeque which is double-sided vector for performance reasons when a doubly linked list would be otherwise used. So the Rust version uses VecDeque even though it may have different performance characteristics from the C++ std::list. The benchmark results shows that the performance differences are small.

Furthermore, the Rust version uses the retain method to remove elements from the VecDeque I believe this is less error-prone than the C++ version where it uses an iteration over the list along with the erase function during the iteration.