Sieve of Eratosthenes in C++ based on Python implementation written by David Eppstein.

prime-sieve.cpp

#include <iostream>
#include <map>
#include <cmath>
#include <vector>

// Sieve of Eratosthenes
//
// This is a simple implementation of the Sieve of Eratosthenes, implemented in
// C++. This is a port of the excellent and very terse implementation by David
// Eppstein[0]. This port is meant to be a straightforward naive port of the
// original to demonstrate the speed difference between Python and C++. This
// code is not optimized for performance, and is the result of me attempting
// only to translate the given Python directly to C++.
//
// In order to get the maximum performance of this program, compile with the
// `-O3` option, e.g.: `g++ -std=c++11 prime-sieve.cpp -O3 -o prime_generator`.
// Then, execute with `./prime_generator`.
//
// [0] - http://code.activestate.com/recipes/117119/


int main(int argc, char** argv){
	std::vector<long long> primes;
	long long q = 2;
	std::map<long long, std::vector<long long>* > nonprimes;

	int prime_count = 1000000;
	if (argc > 1){
		prime_count = atoi(argv[1]);
	}

	while (1){
		if (nonprimes.find(q) == nonprimes.end()){
			primes.push_back(q);
			std::vector<long long>* nv = new std::vector<long long>();
			nv->push_back(q);
			nonprimes[q*q] = nv;
		} else {
			auto witnesslist = nonprimes[q];
			for (auto it = witnesslist->begin(); it != witnesslist->end(); it++){
				auto i = *it;
				if (nonprimes.find(i+q) == nonprimes.end()){
					std::vector<long long>* nv = new std::vector<long long>();
					nv->push_back(i);
					nonprimes[i+q] = nv;
				} else {
					std::vector<long long>* nv = nonprimes[i+q];
					nv->push_back(i);
				}
			}
			delete nonprimes[q];
			nonprimes.erase(nonprimes.find(q));
		}
		if (primes.size() == prime_count){
			std::cout << primes.back() << std::endl;
			return 0;
		}
		/*
		if ((q % 1000) == 0){
			std::cout << q << ": " << nonprimes.size() << std::endl;
			//std::cout << q << ": ";
			//for (auto it = nonprimes.begin(); it != nonprimes.end(); it++){
			//	std::cout << it->first << ", ";
			//}
			//std::cout << std::endl;
		}
		*/
		q++;
	}
}

prime-sieve.rs

use std::collections::HashMap;
use std::collections::hash_map::Entry;
use std::env;

// Sieve of Eratosthenes
//
// This is a "naive" implementation of the sieve of eratosthenese in Rust. It is a port of a very
// terse implementation in Python by David Eppstein[0]. This port is meant to be a comparison
// between the original Python implementation, as well as subsequent implementations in other
// languages (e.g. C++). This naive port of the original is not optimized, nor is it formatted for
// any particular readability. There may be vast swaths of language features that I've missed here
// due to ignorance. Sorry about that.
//
// Example compilation: `rustc prime-sieve.rs -O -o prime_generator`. Then, execute with
// `./prime_generator`
//
// [0] - http://code.activestate.com/recipes/117119/

fn main() {
    let mut primes = Vec::<u64>::new();
    let mut q: u64 = 2;
    let mut nonprimes = HashMap::new();

    let args: Vec<String> = env::args().collect();
    let prime_count =
        if args.len() > 1 {
            let temp: u64 = match args[1].parse() {
                Ok(value) => value,
                Err(_) => panic!("Argument given needs to be an integer.")
            };
            temp
        } else {
            1000000u64
        };

    loop {
        // If subject is prime
        match nonprimes.get(&q).cloned() {
            // If subject is prime
            None => {
                primes.push(q);
                nonprimes.insert(q*q, vec![q]);
            }
            // If subject is NOT prime
            Some(witnesslist) => {
                // Iterate over list of witnesses for subject
                for i in witnesslist {
                    match nonprimes.entry(q + i) {
                        // If witness+subject is not in the list of non-primes
                        Entry::Vacant(entry) => {
                            // Add a new non-prime that's witness+subject with current_witness as it's
                            // initial entry in the witness-list for the new non-prime
                            entry.insert(vec![i]);
                        },
                        Entry::Occupied(entry) => {
                            // Otherwise, add this witness to the list of the non-prime composed of
                            // witness+subject
                            entry.into_mut().push(i);
                        },
                    }
                }
                nonprimes.remove(&q);
            }
        }

        if primes.len() == prime_count as usize {
            println!("{}", primes.last().unwrap());
            break;
        }
        q += 1;
    }
}