使用埃拉托色尼筛法生成 k 个素数

Question

看了几个实现发现，想知道为什么从k = m * m开始迭代是安全的？谢谢

http://www.algolist.net/Algorithms/Number_theoretic/Sieve_of_Eratosthenes

public void runEratosthenesSieve(int upperBound) {
      int upperBoundSquareRoot = (int) Math.sqrt(upperBound);
      boolean[] isComposite = new boolean[upperBound + 1];
      for (int m = 2; m <= upperBoundSquareRoot; m++) {
            if (!isComposite[m]) {
                  System.out.print(m + " ");
                  for (int k = m * m; k <= upperBound; k += m)
                        isComposite[k] = true;
            }
      }
      for (int m = upperBoundSquareRoot; m <= upperBound; m++)
            if (!isComposite[m])
                  System.out.print(m + " ");
}

Answer 1

每个小于 m*m 且 m 是其因数的合数，例如。 m*n，具有比 m 更小的因子，例如。 n，我们已经将其标记为复合。

这适用于质数或合数n，对于质数n，我们在m=n的循环中设置。

对于合数 n：我们知道任何大于 1 的整数都可以表示为质因数的乘积。其中一个质因数是 n 的最小质因数，我们称之为 s。由于 s 是 n 的质因数，对于某些 r，我们可以将 n 表示为 s*r。这也意味着 m*n 是 m*s*r。当 n < m 和 s < n 时，s < m。我们知道 r 没有小于 s 的质因数，因为它是这样定义的。所以s一定是m*s*r的最小质因数，所以我们在m=s的循环中设置它的iscomposite标志

Answer 2

让我们取一个数字并分解它：例如。 120

1 x 120
2 x 60
3 x 40
4 x 30
5 x 24
6 x 20
8 x 15
10 x 12

现在，一个观察：sqrt(120) = 11（发言）

现在，下一次观察，each of the above factors have one thing in common, ie. one of the factors is less than 11 and other is greater than 11。

现在分解 36：

1 x 36
2 x 18
3 x 12
4 x 9
6 x 6

和 sqrt(36) = 6。我们可以再次进行类似的观察，即每个因子都有一个小于 6 的数和另一个大于 6 的数，除了 6 x 6，因为 36 是一个正方形.

所以，我们可以很容易地推导出：

For any number, if it is not a prime number, we can always find (at least) one of its factor, if we go to its square root.

因此，为了降低复杂度，我们需要计算范围内每个数字的平方根，因此，sqrt(upperBound) 足以用于外循环。那是因为，如果任何数字到那时还没有被标记为合数，那将永远不会是合数，因为我们已经考虑了所有可能的除数。

编辑：

此外，这个 sieve 的实现不是 most optimized 可以的。不是在渐近复杂性方面，而是你可以做一些事情来减少一些操作。我将在 C++ 中添加我的 sieve 实现，它计算所有素数直到 MAX。

#define MAX 1000000
#define I int
#define FOR(i,a,b) for(i=a;i<b;i++)
I p[MAX]={1,1,0};            //global declaration
I prime[MAX/10]={2};         //global declaration
void sieve()
{
    I i,j,k=1;
    for(i=3;i*i<=MAX;i+=2)
    {
        if(p[i])
            continue;
        for(j=i*i;j<MAX;j+=2*i)
            p[j]=1;
    }
    for(i = 3; i < MAX; i+=2)
    {
        if(!p[i])
            prime[k++]=i;
    }
    return;
}

使用埃拉托色尼筛法生成 k 个素数

generating k prime numbers using Sieve of Eratosthenes

java

algorithm

primes