# Sieve of Eratosthenes with minimized memory usage [closed]

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<>();
}

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

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);
}

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


The same on python

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

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:

fill_primes(1000)
print(primes)


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

GitHub

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

• Wouldn't it be easier for everybody had you just written it in pseudo code? Jul 13, 2017 at 17:42
• Added visualization and implementation on python Jul 14, 2017 at 6:24

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$.