计算科学 - 最小化内存使用的 Eratosthenes 筛 - 吾爱随笔录

原本 Eratosthenes 的筛子需要大量内存。这个算法是我限制内存使用的尝试。事实上，它需要 ln(N) 内存（对于每个找到的素数，我们保留最后一个交叉数）。

运算量（求和和比较）仍然受到序列 N/2 + N/3 + N/5 + N/7 .... + N/Pk = O(N log log N) 的限制。

算法如下：假设我们有一些找到的素数（描述的算法从 2 和 3 开始）排序。对于每个素数，我们存储与素数相交的最高数。我们引入了一个素数候选数 = 最后找到的素数 + 1（实际上该算法可以跳过偶数，因此我们可以使用最后找到的素数 + 2）。开始检查候选人。对于每个找到的素数，使用最后一个交叉的数字并与候选者进行比较。如果最后一个交叉的小于候选者，则将最后一个交叉的素数增加。如果在下一个增加的候选人等于最后一个交叉之后，那么候选人不是素数（可以除以当前素数），我们应该选择一个新的素数候选人（通过增加当前候选人）。并重新启动算法。如果我们跳过候选人并且最后一个交叉的更大，我们使用下一个素数并对下一个素数的最后一个交叉进行相同的检查。如果每个素数的所有最后交叉都大于候选（跳过候选），我们找到了一个新的素数。找到的素数被添加到找到的素数序列中，最后交叉的被设置为素数。

该算法的源代码在 Java 上表达逻辑。

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

在 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)

当我们选择下一个候选时，仍然可以应用所有基于车轮分解的优化。

GitHub

问题如下 - 上面的算法足够好还是我重新发明了轮子？我的算法复杂度计算是否正确？