Originally sieve of Eratosthenes requires a lot of memory. This algorithm is my attempt to limit the memory usage. In fact it requires ln(N) memory (for each found prime number we keep last crossed number).

Sieve of Eratosthenes visualization Amount of operation (sum and compare) is still limited by sequence N/2 + N/3 + N/5 + N/7 .... + N/Pk = O(N log log N).

Algorithm is following: Suppose we have some found prime numbers (the described algorithm starts from 2 and 3) sorted. For each prime number we store highest number we crossed with the prime. We introduce a prime candidate number = last found prime + 1 (in fact the algorithm can skip even numbers so we can use last found prime + 2). Starting to check the candidate. For each found prime use the last crossed number and compare with the candidate. If the last crossed is less than the candidate increase the last crossed by the prime. If after next increasing candidate equals the last crossed then the candidate is not prime (can be divided by the current prime) and we should choose a new prime candidate (by increasing current candidate). And restart the algoritm. If we jumped over the candidate and last crossed is bigger we use next prime and do the same checks with the last crossed of next prime. If all the last crossed of each prime is bigger than candidate (jumped over the candidate) we found a new prime number. The found prime is added to the found primes sequence and last crossed is set to the prime.

The algorithm's source on Java to express the logic.

import java.util.ArrayList;
import java.util.List;

 * @author stanislav.lapitsky created 7/11/2017.
public class SieveEratosthenes {
    static class PrimePair {
        Integer prime;
        Integer lastCrossed;

        PrimePair(Integer prime, Integer lastCrossed) {
            this.prime = prime;
            this.lastCrossed = lastCrossed;

    private List<PrimePair> primes;

    private SieveEratosthenes() {
        primes = new ArrayList<>();
        primes.add(new PrimePair(2, 2));
        primes.add(new PrimePair(3, 3));

    private void fillNPrimes(int n) {
        while (primes.size()<n) {

    private void addNextPrime() {
        int candidate = primes.get(primes.size()-1).prime + 2;
        for (int i = 1; i < primes.size(); i++) {
            PrimePair p = primes.get(i);
            while (p.lastCrossed < candidate) {
                p.lastCrossed += p.prime;
            if (p.lastCrossed == candidate) {
        primes.add(new PrimePair(candidate, candidate));

    public static void main(String[] args) {
        SieveEratosthenes test = new SieveEratosthenes();

The same on python

primes = [2, 3]
last_crossed = [2, 3]

def add_next_prime():
    candidate = primes[-1] + 2
    i = 0
    while i < len(primes):
        while last_crossed[i] < candidate:
            last_crossed[i] += primes[i]
        if last_crossed[i] == candidate:
            candidate += 2
            i = 0
        i += 1


def fill_primes(n):
    while len(primes) < n:


All the optimization based on wheel factorization is still can be applied when we choose next candidate.


The question is following - Is the algorithm above good enough or I reinvented wheel? Is my algorithm complexity calculation correct or not?

  • 1
    $\begingroup$ Wouldn't it be easier for everybody had you just written it in pseudo code? $\endgroup$
    – Yair Daon
    Jul 13, 2017 at 17:42
  • $\begingroup$ Added visualization and implementation on python $\endgroup$
    – StanislavL
    Jul 14, 2017 at 6:24

1 Answer 1


It is better to state the complexity based on the sum of the reciprocals of the primes, which is correctly pointed to grow at the indicated rate of $\ln \ln N$.


For the space complexity, you are looking at the 'prime counting function', which grows at $\frac{N}{\ln N}$ as opposed to $\ln N$.


The algorithm implementation is just the conventional 'Sieve of Eratosthenes', but described in a complicated fashion.

  • $\begingroup$ Thank you for the pointing. I see my error in the memory usage estimation. I should consider ln(1000) is much less than prime numbers count $\endgroup$
    – StanislavL
    Jul 18, 2017 at 5:36

Not the answer you're looking for? Browse other questions tagged or ask your own question.