Eratosthenes sieve, attempt to minimize memory

Introduction

One of the algorithms for finding prime numbers is the Sieve of Eratosthenes proposed by the ancient Greek mathematician.

Wikipedia picture:


The point is to cross out the numbers of multiples already found simple. Remaining unstressed in turn are simple. More detailed here .

One of the problems when searching for a sieve is the amount of memory that needs to be allocated for filtered numbers. Crossed out difficult ones are deleted, reducing memory, but initially a large amount is required.

To solve this, segmentation is used (when memory is allocated in pieces) and other tricks (see here ).

Algorithm implementation

The algorithm below (written in java) assumes a minimum amount of memory - in fact, for each found prime, we store another number - the last one crossed out (the largest). If I correctly estimate the memory size ln (n) - the number of primes found.

The essence of the algorithm:

Suppose we have several primes already found sorted in ascending order. (The algorithm starts with [2,3]). For each of them, store the last (largest) strikethrough number. We initialize by the primes themselves.

We select a candidate for prime, for example, the largest prime number +1 found (in the algorithm below, we skip even ones that are obviously not simple).

The candidate is compared to the last strikeout of the current prime. While the current strikeout is less than the candidate, we increase it by the current prime. If the current strikethrough is equal to the candidate, then the candidate is not a prime. Choose the next candidate.

If the current strikeout is greater than the candidate, check the candidate on the next prime number.

If we got to the end of the list of prime numbers (that is, all those crossed out more than the candidate), we found another prime number.

Add it to the list and initialize the last crossed out by the found simple.

Java code

import java.util.ArrayList;
import java.util.List;
public class SieveEratosthenes {
    static class PrimePair {
        Integer prime;
        Integer lastCrossed;
        PrimePair(Integer prime, Integer lastCrossed) {
            this.prime = prime;
            this.lastCrossed = lastCrossed;
        }
    }
    private List 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()

Тот же код на питоне:

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
    primes.append(candidate)
    last_crossed.append(candidate)
def fill_primes(n):
    while len(primes) < n:
        add_next_prime()
fill_primes(1000)
print(primes)

Вся логика традиционных алгоритмов с колесами может быть применена при выборе следующего кандидата.

→ GitHub

Возможно это очередное изобретение велосипеда. Готов выслушать замечания.