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).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) {            addNextPrime();        }    }    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) {                //restart                candidate+=2;                i=1;            }        }        System.out.println(candidate);        primes.add(new PrimePair(candidate, candidate));    }    public static void main(String[] args) {        SieveEratosthenes test = new SieveEratosthenes();        test.fillNPrimes(1000);    }}The same on pythonprimes = [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    primes.append(candidate)    last_crossed.append(candidate)def fill_primes(n):    while len(primes) < n:        add_next_prime()fill_primes(1000)print(primes)All the optimization based on wheel factorization is still can be applied when we choose next candidate.GitHubThe question is following - Is the algorithm above good enough or I reinvented wheel? Is my algorithm complexity calculation correct or not?
Sieve of Eratosthenes with minimized memory usage
optimization;algorithms
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$. https://en.wikipedia.org/wiki/Divergence_of_the_sum_of_the_reciprocals_of_the_primesFor the space complexity, you are looking at the 'prime counting function', which grows at $\frac{N}{\ln N}$ as opposed to $\ln N$.https://en.wikipedia.org/wiki/Prime-counting_functionThe algorithm implementation is just the conventional 'Sieve of Eratosthenes', but described in a complicated fashion.