Странная ошибка сегментации в C большой массив с Clang

Question

Здесь я хочу найти сумму всех простых чисел ниже двух миллионов. Я использую сито Эратосфена, поэтому мне нужен массив из двух миллионов.

Сначала я объявляю массив только как глобальную переменную, но zsh дает мне ошибку сегментации. Так что я попробовал malloc, но ошибка все еще там. Я уже тестирую небольшой массив, программа работает нормально.

Кроме того, я использую clang-1000.10.44.2, с -O2 программа может работать, но ответ неверный. Код ниже.

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

#define MAXN 2000000

unsigned long long sum;
void erat(int maxn, char *flag)
{
    flag[0] = 0;
    flag[1] = 0;
    for(int i = 2; i < maxn; i++)
        if(flag[i])
            for(int j = i * i; j < maxn; j+=i)
                flag[j] = 0;
}

int main()
{
    int i;
    char *flag = (char*) malloc(MAXN * sizeof(char));
    for(i = 0; i < MAXN; i++)
        flag[i] = 1;
    erat(MAXN, flag);
    for(i = 0; i < MAXN; i++)
        if(flag[i]) sum+=i;
    printf("%llu\n", sum);
    return 0;
}

Надеюсь, кто-нибудь может мне помочь, спасибо за ваше время!

Answer 1

Вы переполняете int здесь:

for (int j = i * i; j < maxn; j+=i)

Поскольку i достигает 2000000, i*i может быть больше, чем 2 ³¹ , что приводит к переполнению и неопределенному поведению .

Вы можете обратиться к этому во внешнем цикле:

for(int i = 2; i < maxn; i++)

Вам нужно только проверить квадратный корень из maxn, поэтому измените его на:

for(int i = 2; i * i < maxn; i++)

Answer 2

Когда i равно 46349, i*i равно 2148229801, это больше, чем уходит в целое число, поэтому переполняется до -2146737495, так как это меньше, чем maxn, выполняется flag[j] = 0, что выходит за пределы массива, поэтому вылетает.

Изменение j на long long исправляет ошибку:

for (long long j = (long long)i * i; j < maxn; j += i)