1
$\begingroup$

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) {
            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 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 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?

$\endgroup$

closed as off-topic by Bill Greene, Christian Clason, nicoguaro, Kirill, Paul Jul 18 '17 at 20:17

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "General computer science questions are off-topic here, but can be asked on Computer Science Stack Exchange." – Bill Greene, Christian Clason, nicoguaro, Kirill, Paul
If this question can be reworded to fit the rules in the help center, please edit the question.

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

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_primes

For 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_function

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

$\endgroup$
  • $\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 '17 at 5:36

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