c - 我找不到内存泄漏。 (SIGSEGV)(埃拉托色尼分段筛)(C)

Question

我正在尝试用 C 语言(我是初学者程序员)实现埃拉托色尼分段筛，它只是打印正确的输出，但当我在 SPOJ 上提交时，我收到了 SIGSEGV。你能帮我找出漏洞吗？

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

void segmented_sieve(int *m, int *n, int t) {
int count, i, j, l, sqrt_imax, hlp_imin;
count = i = j = l = sqrt_imax = hlp_imin = 0;
int *imin, *imax;
imin = m;
imax = n;
sqrt_imax = (int)sqrt((double)imax[t]);
int *sieve;
sieve = malloc((imax[t] + 1) * sizeof(*sieve));
memset(sieve, 1, (imax[t] + 1) * sizeof(*sieve));
for (i = 2; i <= sqrt_imax; ++i) {
    for (j = i * i; j <= imax[t]; j += i)
        sieve[j] = 0;
}
int *next;
next = malloc((int)sqrt(1000000000) * sizeof(*next));
for (i = 2; i <= sqrt_imax; ++i) {
        if (sieve[i] > 0) {
                ++count;
                next[count] = i;
        }
}
for (i = 1; i <= count; ++i) {
    if (imin[t] <= 2) {
        imin[t] = 2;
        for (j = next[i]; j <= sqrt_imax; j = next[i]) {
            for (l = j * j; l <= n[t]; l += j)
                sieve[l] = 0;
            break;
        }
    }
    else {
        hlp_imin = (int)(m[t] / next[i]);
        hlp_imin *= next[i];
        for (j = next[i]; j <= sqrt_imax; j = next[i]) {
                for (l = hlp_imin; l <= imax[t]; l += j)
                        sieve[l] = 0;
                break;
        }
    }
}
for (i = imin[t]; i < imax[t]; ++i)
    sieve[i] > 0 ? printf("%d\n", i) : 0;
free(sieve);
free(next);
}

int main()
{
int t, tmp, i;
t = tmp = i = 0;
scanf("%d", &t);
int *m;
m = malloc(t * sizeof(*m));
int *n;
n = malloc(t * sizeof(*n));
for (i = 0; i < t; ++i) {
    scanf("%d", &tmp);
    m[i] = tmp;
    scanf("%d", &tmp);
    n[i] = tmp;
}
for (i = 0; i < t; ++i) {
    segmented_sieve(m, n, i);
    printf("\n");
}
free(m);
free(n);
return 0;
}

我通过将 int 更改为 char 来修复它。现在刚刚获得 TLE...

Answer 1

考虑一下如果得到两个值 imin = 2,000,000,000 和 imax = 2,000,000,010 会发生什么。您应该创建一个仅容纳 11 个数字的小筛子。但是您分配的存储空间为 20 亿个整数，这可能超出了您的计算机的处理能力。