Sieve of Eratosthenes, an attempt to minimize memory

Introduction

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

Picture from Wikipedia:


Meaning in crossing out multiples already found simple. The remaining unclosed in turn are simple. More detailed here .
')
One of the problems when searching with sieves is the amount of memory that needs to be allocated to the filtered numbers. Crossed out uneasy are removed reducing memory, but initially the volume required is large.

For the solution, segmentation is used (when memory is allocated in pieces) and other tricks (see here ).

Algorithm implementation

The algorithm below (written in java) assumes the minimum amount of memory - in fact, for each found simple number we store one more number - the last crossed out (largest). If I correctly estimate the amount of memory 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) number crossed out. Initialize by the primes themselves.

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

The candidate is compared with the last crossed out the current simple. So far, the current crossed out less candidate increase it to the current simple. If the current strikeout is equal to the candidate, then the candidate is not a prime number. Choose the next candidate.

If the current crossed out is more than the candidate, check the candidate for the next prime number.

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

Add it to the list and initialize the last crossed out 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<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 code 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 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 logic of traditional algorithms with wheels can be applied when choosing the next candidate.

→ GitHub

Perhaps this is another invention of the bike. Ready to listen to comments.