为什么第一个质数总是变成 1 而不是 2

Question

这里我正在尝试在 c.The 程序中实施埃拉斯托色筛法工作正常，除了一个主要 problem.I 手动将第一个质数设置为值 2.But 最后当我循环遍历所有素数数组并打印它们，第一个值变为 1 而不是 2.Can 不明白为什么会出现此问题 arises.Any 帮助将不胜感激。

#include<stdio.h>
#include<math.h>
int main(){

    int n = 64;
    int i,j,limit=sqrt(n)+2,nPrime=0;
    int prime[50]={0},mark[64]={0};
    mark[1]=1;

    prime[nPrime++] = 2;
    printf("%d\n",prime[0]); // initialized to 2



    for(i=4;i<=n;i=i+2){
       mark[i] = 1;
    }
    for(i=3;i<=n;i=i+2){
       if(!mark[i]){
           prime[nPrime++] = i;
           if(i<=limit){
              for(j=i*i;j<=n;j=j+i*2){
                 mark[j]=1;
              }
           }
       }
    }
    int k;
    int size = sizeof(prime)/sizeof(prime[0]);
    printf("%d\n",prime[0]);  // changed to 1;
    for(k=0;k<size && prime[k]!=0;k++){
        printf("%d ",prime[k]);
    }

}

Answer 1

问题出在这个循环中：

for(i=4;i<=n;i=i+2) {
    mark[i] = 1;
}

条件应该是i < n，因为<= 它将取值64，这将超出范围。

当你设置mark[64] = 1时，你正在修改不属于标记数组的内存，在这种情况下它变成了素数数组的第一个元素。如果您测试其他索引，您最终可能会遇到段错误。

如果您手动设置 mark[64] = 56，您会看到 prime[0] == 56

Answer 2

因为局部变量是在堆栈上声明的，在你的例子中，变量 mark[64] 是一个 64 整数数组（64 * 4 = 256 字节）占据堆栈的前 256 个字节，然后是数组素数（ 50 * 4 = 200 bytes）占用接下来的200 bytes如下图：

                           Stack
                       |-----------|
                       |   other   |
                       | variables |
                       |           |
            prime[49]->|-----------| addr = 0x000001C8
                       |           |
                       |   prime   |
                       |(200 bytes)|
             prime[0]->|           |
             mark[63]->|-----------| addr = 0x00000100 
                       |           |
                       |           |
                       |   mark    |
                       |(256 bytes)| 
                       |           |
              mark[0]->|-----------| addr = 0x00000000

当你写mark[64] = 1时，实际上是在写prime[0] = 1的四个字节。

为什么第一个质数总是变成 1 而不是 2

Why the first prime number always becoming 1 instead of 2

c

sieve-of-eratosthenes