c++ - 段错误 C++ Sundaram

Question

我的程序的主要目标是打印 2 和极限之间的所有素数。当我使用 limit = 35000 甚至 limit = 50000 运行它时，它打印正确，但是当我尝试使用 limit = 75000 运行它时，它给我一个段错误。知道为什么吗？有什么我可以做的来获得更好的表现吗？ (基于Sundaram算法的解决方案)

#include <stdio.h>
#include <stdlib.h>


#define MAX 1000000



int main() {
    int vetor[MAX];
    int limite;

    scanf("%d", &limite);


    for (int i = 0; i <= limite; i++){
      vetor[i] = i;
    }

    /* Marcar todos os compostos */
    for (int i = 1; i < limite/2; i++){
      for (int j = i;  j< limite/2; j++){
        long aux = i + j + 2 * i * j;
        if(aux <= limite)
          vetor[aux] = 0;
      }
    }

    /* Imprimir os verdadeiros primos, incluíndo o 2 */
    printf("2\n");

    for (int i = 1; i <= limite; i++){
      if (vetor[i] != 0){
        long aux = i*2 + 1;
        if (aux < limite){
          printf("%ld\n",aux);
        }
      }
    }

   return 0;
}

Answer 1

试试这个。我将 i、j 和 aux 更改为“unsigned long long”。你的问题是溢出。这意味着您的整数大于最大整数值。希望 int 不是最大的整数数据类型。最大的是 unsigned long long。但无论如何请记住，您遇到此问题的时间仍然有限。

#include <stdio.h>
#include <stdlib.h>


#define MAX 1000000



int main() {
    int vetor[MAX];
    int limite;

    scanf("%d", &limite);


    for (int i = 0; i <= limite; i++){
        vetor[i] = i;
    }

    /* Marcar todos os compostos */
    for (unsigned long long i = 1; i < limite/2; i++){    
        for (unsigned long long j = i;  j< limite/2; j++){
            unsigned long long aux = i + j + 2 * i * j;
            if(aux <= limite)
                vetor[aux] = 0;
        }
    }

    /* Imprimir os verdadeiros primos, incluíndo o 2 */
    printf("2\n");

    for (int i = 1; i <= limite; i++){
        if (vetor[i] != 0){
            long aux = i*2 + 1;
            if (aux < limite){
                printf("%ld\n",aux);
            }
        }
    }

    return 0;
}