c - 在 C 中设计 eratosthenes 筛时减少内存使用

Question

我正在尝试用 C 语言设计埃拉托色尼筛，但我遇到了两个我无法弄清楚的奇怪问题。这是我的基本程序大纲。要求用户设置显示素数的范围。如果范围最小值低于 9，则将最小值设置为 9。用范围内的所有奇数填充一个数组。

1) 我正在尝试通过声明可变大小数组来减少内存使用:

    if (max<=UINT_MAX)
       unsigned int range[(max-min)/2];
    else if (max<=ULONG_MAX)
         unsigned long int range[(max-min)/2];
    else if (max<=ULLONG_MAX)
         unsigned long long int range[(max-min)/2];

为什么不能编译？变量 min 和 max 之前被声明为 ints 并且包含了 limits.h。我已经注释掉了选择结构并声明了 unsigned long long int range[(max-min)/2]; 现在可以编译和工作了。

2) 我的代码可以运行，但有时会将小素数标记为非素数。

#include<stdio.h>
#include<limits.h>

void prime(int min, int max)
{
    int i, f=0;
    //declare variable size array
    /*if (max<=(int)UINT_MAX)
       unsigned int range[(max-min)/2];
   else if (max<=(int)ULONG_MAX)
         unsigned long int range[(max-min)/2];
    else if (max<=(int)ULLONG_MAX)*/
         unsigned long long int range[(max-min)/2];
    //fill array with all odd numbers
    if (min%2==0)
    {
        for (i=min+1;i<=max;i+=2)
        {
            range[f]=i;
            f+=1;
        }
    }
    else
    {
        for (i=min;i<=max;i+=2)
        {
            range[f]=i;
            f+=1;
        }
    }
    //assign 0 to cell if divisible by any number other than itself
    for (i=3;i<=sqrt(max);++i)
    {
        for (f=0;f<=((max-min)/2);f++)
        {
            if (range[f]%i==0 && f!=i)
                range[f]=0;
        }
    }
    //troubleshoot only: print full range
    for (f=0;f<=((max-min)/2);f++)
    {
            printf("ALL: %d / %d\n", f, range[f]);
    }    
    //display all primes
    if (min==9) /*print primes lower than 9 for ranges where min<9*/
            printf("2\n3\n5\n7\n");
    for (f=0;f<=((max-min)/2);f++) /*print non 0 numbers in array*/
    {
        if (range[f]!=0)
            printf("%d\n", range[f]);
    }
}
int main(void)
{
    int digits1, digits2;
    printf("\n\n\nCalculate Prime Numbers\n");
    printf("This program will display all prime numbers in a given range. \nPlease set the range.\n");
    printf("Minimum: ");
    scanf("%d", &digits1);
    if (digits1<9)
       digits1=9;
    printf("Maximum: ");
    scanf("%d", &digits2);
    printf("Calculating...");
    printf("All prime numbers between %d and %d are:\n", digits1, digits2);
    prime(digits1, digits2);
    getchar();
    getchar();
}

例如，如果 digits=1 和 digits2=200，我的程序输出 1 到 200 之间的所有质数，除了 11 和 13。11 和 13 被筛掉了，我不明白为什么越来越多的小数会发生这种情况随着 digits2 的增加。

3) 最后，我的筛子是埃拉托色尼的合适筛子吗？它有点管用，但我觉得有一种更有效的方法可以筛选出非素数，但我不知道如何实现它。我对这个程序的目标之一是尽可能高效。同样，我现在拥有的是:

    //assign 0 to cell if divisible by any number other than itself
    for (i=3;i<=sqrt(max);++i)
    {
        for (f=0;f<=((max-min)/2);f++)
        {
            if (range[f]%i==0 && f!=i)
                range[f]=0;
        }
    }

感谢您阅读所有内容!很抱歉发布了另一个与埃拉托色尼相关的问题，在此先感谢您的帮助!

Answer 1

不，这不是埃拉托色尼筛法。 Eratosthenes 算法的筛法不涉及余数测试，Wikipedia is real clear on this我认为。 :) 它的全部意义在于避免试验 split ，免费获得素数，无需测试。

如何？通过生成它们的倍数，从我们识别的每个质数中，一个接一个地升序。

素数 p 的倍数是:2p, 2p + p, 2p + p + p, ...

素数的奇数倍数 p 是:3p, 3p + 2p, 3p + 2p + 2p, ...

当我们枚举它们时，我们在筛选数组中标记它们。有些会被标记两次或更多次，例如15 将被标记为 3 和 5(因为 3 * 5 == 5 * 3)。因此，我们可以从p²开始枚举和标记:

  for( i=3; i*i < n; i += 2 )
      if( !sieve[i] )         // if `i` is not marked as composite
          for( j = i*i; j < n; j += 2*i )
          {
              sieve[j] = 1;   // 1 for composite, initially all are 0s
          }

筛子的关键在于:我们不将数字 存储在数组中。它不是 INT 的数组;它是一个 1 位标志数组，值为 0 或 1。筛子数组中条目的索引表示筛子保持其状态的数字:已标记，即复合，或尚未标记，即潜在素数。

所以最后，所有未标记的条目都表示素数。您当然需要设计一个寻址方案，例如索引 i 处的条目可能对应于数字 a + 2*i其中 a是范围的奇数开始。由于您的范围从某个偏移量开始，因此该方案称为 offset sieve of Eratosthenes .骨架 C 实现是 here .

为了尽量减少内存使用，我们需要将数组视为位数组。在 C++ 中，例如很简单:我们将其声明为 vector<bool>它会自动为我们进行位压缩。在 C 中，我们必须自己进行一些打包和解包操作。

忠告:不要吝啬临时变量。命名程序中每个有意义的实体。不应该有任何 (max-min)/2在你的代码中；而是定义 width = max - min并使用那个名字。将小的优化留给编译器。 :)

---

第一个问题:这是一个范围的问题。你的代码等同于

if (max<=UINT_MAX)
    {   unsigned int range[(max-min)/2]; }    // note the curly braces!
else if (max<=ULONG_MAX)
    {   unsigned long int range[(max-min)/2]; }
else if (max<=ULLONG_MAX)
    {   unsigned long long int range[(max-min)/2]; }

所以有三个 range这里的数组声明，每个都在其自己的范围内，在相应的 block 内。每个都在进入其封闭 block ({)时创建，并在退出时被销毁(})。换句话说，它不存在于您的 prime 的其余部分。功能了。实际上这意味着如果你在 if 中声明你的变量 block ，您只能在该 block 内使用它(在相应的大括号 { 和 } 之间)。