CODEWITHSUNDEEP
cclang
Obsessive
Obsessive

Reputation: 69

Weird segmentation fault in C big array with clang

Here i want to find the sum of all the primes below two million. I use sieve of Eratosthenes so i need a two million array.

At first, i only declare the array as a global variable, but zsh give me a segmentation fault.So i tried malloc but the error still there. I already test small array the program works fine.

Besides, i use clang-1000.10.44.2, with -O2 the program can work but the answer is incorrect.The code is below.

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

Hope someone can help me, thanks for your time!

Upvotes: 0

Views: 417

Answers (2)

dbush
dbush

Reputation: 224437

You're overflowing an int here:

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

Since i goes up to 2000000, i*i can be larger than 231, resulting in overflow and undefined behavior.

You can address this in the outer loop:

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

You only need to check up to the square root of maxn, so change it to:

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

Upvotes: 1

Alan Birtles
Alan Birtles

Reputation: 36488

When i is 46349, i*i is 2148229801, this is more than fits in an integer so overflows to -2146737495, as this is less than maxn, flag[j] = 0 is executed which is out of bounds of the array so crashes.

Changing j to long long fixes the bug:

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

Upvotes: 5

Related Questions