3

我猜下面的方法使用埃拉托色尼筛法（包含 - 排除算法）来生成最多给定数字的素数。我特别不明白的是，为什么它会清除该位置上设置的(j/2)位。是否遵循特定的规则？包含在位置 x 处设置的BitSet位，并且该数字是质数或复合数。所以，我无法了解正在发生的事情。

public static List<Integer> generatePrimes(int max) {
        BitSet primeSet = new BitSet(max / 2);
        primeSet.set(1, max / 2);
        int limit = (int) Math.sqrt(max);
        for (int i = 3; i <= limit; i += 2) {
            if (!primeSet.get(i / 2)) continue;
            for (int j = i * i; j < max; j += i * 2)
                primeSet.clear(j / 2);

        }

        List<Integer> listOfPrimes = new ArrayList<>();
        listOfPrimes.add(2);
        for (int i = primeSet.nextSetBit(0); i >= 0; i = primeSet.nextSetBit(i + 1)) {
            listOfPrimes.add(i * 2 + 1);
        }
        return listOfPrimes;
    }
4

4 回答 4

2 
public static List<Integer> generatePrimes(int max) {

 BitSet primeSet = new BitSet(max / 2);  // host the numbers i up to max/2
 primeSet.set(1, max / 2);               // representing the odds (2i+1)
 int limit = (int) Math.sqrt(max);       //                      below max
 for (int i = 3; i <= limit; i += 2)        // enumerate odds in range 
 {                                          //       3 .. sqrt(max)
     if (!primeSet.get(i / 2)) continue;    // i=2k+1, i/2==(2k+1)/2== k
                                            // (here i is value, k is index)
     for (int j = i * i; j < max; j += i * 2)  // j=i*i is the first multiple
         primeSet.clear(j / 2);        // of i, where the marking off begins
 }                                     //  with step 2*i: 3: 9,6,15,21,...
                                       //                 7: 49,63,77,91,...
 List<Integer> listOfPrimes = new ArrayList<>();
 listOfPrimes.add(2);                     // 2 is known to be prime a priori
 for (int i = primeSet.nextSetBit(0);     // starting with first set bit in
                                          //                 BitSet primeSet,
          i >= 0;                         // 1: until the end of primeSet  
          i = primeSet.nextSetBit(i + 1)  // 3: and go to next set bit
          ) {
     listOfPrimes.add(i * 2 + 1);         // 2: add 2i+1 to the list of primes,
 }                                        // (here i is index)
 return listOfPrimes;
}

作为筛子的一部分，我们必须在赔率中从 9 开始标记每个第三个数字，并且通常从n 2开始标记每个第n个数字，正如一位Rev. Samuel Horsley FRS 早在 1772 年就知道的那样。

仅沿列表计数是低效的——筛子效率的关键是通过地址直接访问内存。这里的数字数组中的数字的地址就是数字本身的值（这种值和地址的混淆也是各种整数排序方法效率的关键）。

要直接计算每个第三个奇数，我们必须在前一个奇数上加 6 才能得到下一个奇数。对于每 5 个，我们添加 10，并且对于每个ith – 2*i。

顺便说一下，这段代码可以稍微改进。对于2*i它们之间距离的数字，集合中的索引将在距离i. 无需一直删除 2，只需计算起始索引并递增i.

编辑：该代码等效于以下伪代码：

defn primes(max):
  sieve := makeArray(3,5,7 ... max, True)
  for p from 3 to sqrt(max) step 2:
    if sieve[p]:
        for i from p * p to max step 2*p:
            sieve[i] := False
  primes = {2} + {all i in (3,5,7, ... max) such that sieve[i] is True}
于 2013-05-11T14:56:18.533 回答
2

该算法似乎试图通过仅primeSet表示奇数来节省内存。因此，重复的乘法和除以二。

涉及的循环primeSet.clear()只是将每个倍数标记i为复合。

于 2013-05-11T09:55:58.117 回答
1

除 2 之外的所有偶数都不是素数，因此无需迭代它们。

于 2013-05-11T09:59:49.517 回答
1

素数集的位表示数字 2x+1，其中 x 是位集的索引。因此，当您的素数集包含 {1, 2, 3, 5, 6, 8, 9, 11, 14} 时，它们代表数字 {3, 5, 7, 11, 13, 17, 19, 23, 29}。

如果你对使用素数编程感兴趣，我在我的博客上谦虚地推荐这篇文章。除其他外，它解释了埃拉托色尼筛法和导致你悲伤的计算。

编辑：添加简单的 Eratosthenes 筛，如评论中所述。

function primes(n)
    sieve := makeArray(2..n, True)
    for p from 2 to n step 1
        if sieve[p]
            output p
            for i from p * p to n step p
                sieve[i] := False
于 2013-05-11T12:35:48.160 回答