Skip to content

Instantly share code, notes, and snippets.

@BenGoldberg1
Last active September 21, 2017 23:31
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save BenGoldberg1/66ef4fb63e2b836366c34b0f8108d906 to your computer and use it in GitHub Desktop.
Save BenGoldberg1/66ef4fb63e2b836366c34b0f8108d906 to your computer and use it in GitHub Desktop.
#include <iostream>
#include <deque>
typedef std::deque<unsigned> intlist;
typedef std::deque<intlist> listlist;
void my_insert( listlist & factors, unsigned factor ) {
if( factor >= factors.size() ) factors.resize( factor+1 );
factors[ factor ].push_back( factor );
}
int main() {
intlist primes;
listlist factors;
unsigned a_prime = 3, a_square_prime = 9, maybe_prime = 3;
factors.resize(3);
std::cout << "2 3 ";
while( maybe_prime <= 999 ) {
intlist &f = factors.front();
maybe_prime += 2;
if( !f.empty() ) {
intlist::iterator i = f.end();
while( i != f.begin() )
my_insert( factors, *(--i) );
} else if( maybe_prime < a_square_prime ) {
std::cout << maybe_prime << " ";
primes.push_back( maybe_prime );
} else {
my_insert( factors, a_prime );
a_prime = primes.front();
primes.pop_front();
a_square_prime = a_prime * a_prime;
}
factors.pop_front();
}
std::cout << std::endl;
return 0;
}
@BenGoldberg1
Copy link
Author

BenGoldberg1 commented May 3, 2016

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment