incremental sieve of eratosthenes

While writing and testing okp, I wrote a quick incremental prime sieve. The sieve of eratosthenes is a fast way of calculating primes between 1..n. It works by keeping track of all primes from 1..n and for each prime, iterate over its multiples and mark them as non-prime.

The sieve takes up O(N) space and has a time complexity of O(N sqrt N). A minor optimization is that it grows by powers of 2, so if we ask for subsequent primes, we re-calculate infrequently.

Source

#include <cmath>
class Sieve:
    vector<int> values
    int last_max
public:
    Sieve():
        // 0 is prime, 1 is prime, 2 is prime, 3 is prime
        // the rest follow from that
        values = { 0, 0, 0, 0 }
        self.last_max = 3
    def resize(int n)
    def make_sieve(int n)
    def is_prime(int n)

def Sieve::resize(int n):
    s = self.values.size()
    while n >= s:
        s <<= 1
    self.values.resize(s+1)
    return s

def Sieve::make_sieve(int n):
    // we don't want to continually re-build our sieve,
    // so we rebuild in powers of 2
    n = self.resize(n)
    m = ceil(sqrt(n))
    for i = 2; i <= m; i++:
        if self.values[i]: // values[i] is not prime if true
            continue
        lm = max(self.last_max / i+1, 2)
        for j = lm; j * i <= n; j++:
            self.values[j*i] = 1
    self.last_max = n

def Sieve::is_prime(int n):
    if self.values.size() <= n:
        self.make_sieve(n)
    return self.values[n] == 0

def is_prime(int n):
    for i = 2; i < n; i++:
        if n % i == 0:
            return false
    return true

int main():
    s = Sieve()
    m = 1000
    all_good = true
    for k = 0; k < m; k++:
        if is_prime(k) != s.is_prime(k):
            print k, s.is_prime(k), is_prime(k)
            all_good = false
    if all_good:
        print "ALL GOOD!"
    else:
        print "A PROBLEM WAS FOUND"

okay

Source