A simple sieve for prime numbers

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;

     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;

          /* 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.

Please follow and like us:

Leave a Reply

Your email address will not be published. Required fields are marked *