The Ancient world knew of the Sieve of Eratosthenes for generating prime numbers. The algorithm works by keeping track of integers and marking them off if they are a multiple of a prime. As one continues through the list, we discover numbers that aren’t marked off, and therefore know that those numbers are prime.

There is a major problem with this approach, and that is its limited in the size of the array needed to keep track of the integers. A simple way to implement the sieve without using an array buffer to track the integers follows:

/* Copyright (C) 2017, ObjectSoftware.biz, All Rights Reserved. * Presented under the GPL v2 license. */ #include "int.h" typedef list<int_t> list_t; list_t seive(int_t limit) { list_t primes; primes.push_back("2"); for(int_t i = int_t::THREE; i < limit; i++) { int_t sqrt = i.sqrt(); for(list_t::iterator j = primes.begin(); j != primes.end(); j++) { if((*j) > sqrt) { goto IS_PRIME; } if((i % (*j)) == int_t::ZERO) { goto IS_COMPOSITE; } } IS_PRIME: primes.push_back(i); i.print(stdout); IS_COMPOSITE: /* no-op */; } return primes; }

The above implementation assumes an arbitrary precise integer class called int_t which we will discuss in another post. Suffice it to say that the class uses GMP for integer and floating point calculations and is just a simple wrapper in C++.

Notice that the algorithm uses the discovered primes to verify if the next number is prime and proceeds to build a list of primes without keeping track of all integers the way the classic sieve does. The algorithm was used to generate the first 32 bit primes.