在C语言设计eratosthenes筛时减少内存消耗

Question

我正试图用C语言设计一个eratosthenes筛子，但我遇到了两个奇怪的问题，我无法解决。这是我的基本程序大纲。要求用户设置一个显示素数的范围。如果范围最小值低于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的增加，越来越低的数字会出现这种情况。

最后，我的筛子是埃拉托斯提尼的合适筛子吗？这有点工作，但我觉得有一种更有效的方法筛选出非素数，但我不知道如何实现它。我这个项目的目标之一是尽可能提高效率。再说一次，我现在拥有的是：

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

谢谢你阅读了所有这些！很抱歉，我张贴了另一个筛子与eratosthenes有关的问题，并感谢您的帮助提前！

Answer 1

Q1:您不能在同一范围内两次声明符号(此处为：range)。这并不完全是您的问题，但您正在尝试这样做:您在if范围内声明了if，并且它在外部不可见。