prime_finder.cpp

#include <cstdio>
#include <set>

#include <gmpxx.h>

int main(int argc, char** argv) {
	// Set upper bound
	mpz_class max;
	{
		unsigned int maxpow2 = 8;
		if(argc > 1) sscanf(argv[1], "%ud", &maxpow2);
		mpz_ui_pow_ui(max.get_mpz_t(), 2, maxpow2);
	}
	// Init sieve
	std::set<mpz_class> primes;
	primes.insert(2);
	primes.insert(3);
	puts("2\n3");
	// Start searching
	mpz_class current(4);
	do {
		// All primes are 6k \pm 1 for k \in \bbold{N}
		mpz_class six_k = current % 6;
		if(six_k != 1 && six_k != 5) continue;
		// Sieve of Eratosthenes
		mpz_class erat_max = sqrt(current);
		bool erat_isp = true;
		for(mpz_class p : primes) {
			if(current % p == 0) {
				erat_isp = false;
				break;
			} else if(p >= erat_max) {
				break;
			}
		}
		if(!erat_isp) continue;
		// Output prime and add to set.
		mpz_out_str(stdout, 10, current.get_mpz_t());
		putc('\n', stdout);
		primes.insert(current);
	} while(++current < max);
	return 0;
}