C语言 Malloc() 在使用长长数据类型时失败

Question

下面的代码打印出[m，n]之间的所有素数。 当我使用无符号 int 时，malloc 在我的 64 位系统上可以完美地工作，直到10^9预期。

#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <stdlib.h>
#include <time.h>
#define true 1 
#define false 0
void SieveOfEratosthenes(unsigned int m ,unsigned int n) {
bool *prime;
prime = (bool*)malloc(m - n + 2);
if (!prime) {
printf("FAILn");
return;
}
memset(prime, true, (m - n + 2));
unsigned int i = 2;
for (i = 2; i * i <= n; i++) {
if (prime[i] == true) {
for (unsigned int j = i * 2; j <= n; j += i)
prime[j] = false;
}
}
for (i = m; i <= n; i++)
if (prime[i] && i != 1)
printf("%u  n", i);
}
int main() {
clock_t begin,end;
unsigned int m, n;
scanf("%u %u", &m, &n);
begin = clock();
SieveOfEratosthenes(m, n);
end = clock();
double time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
printf("nTime Taken : %lf secsn", time_spent);
return 0;
}

但是当我从unsigned int更改为unsigned long long时，对于较大的值，malloc每个值都失败，即使是小值。为什么这不起作用？

#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <stdlib.h>
#include <time.h>
#define true 1 
#define false 0
void SieveOfEratosthenes(unsigned long long m, unsigned long long n) {
bool *prime;
prime = (bool*)malloc(m - n + 2);
if (!prime) {
printf("FAILn");
return;
}
memset(prime, true, (m - n + 2));
unsigned long long i = 2;
for (i = 2; i * i <= n; i++) {
if (prime[i] == true) {
for (unsigned long long j = i * 2; j <= n; j += i)
prime[j] = false;
}
}
for (i = m; i <= n; i++)
if (prime[i] && i != 1)
printf("%llu  n", i);
}
int main() {
clock_t begin,end;
unsigned long long m, n;
scanf("%llu %llu", &m, &n);
begin = clock();
SieveOfEratosthenes(m,n);
end = clock();
double time_spent=(double)(end - begin) / CLOCKS_PER_SEC;
printf("nTime Taken : %lf secsn", time_spent);
return 0;
}                                                                                                                                                                                                                

Answer 1

由于以下原因，您的代码具有未定义的行为：

unsigned int m, n;
scanf("%llu %llu", &m, &n);

此外，您没有分配适当的内存量：

prime = (bool*)malloc(m - n + 2);

如果m小于n + 2，则大小变成一个巨大的数字。它只适用于unsigned int，因为您可以在系统上分配 4GB 或可能 16GB 的内存。

事实上，给定你的算法，你必须分配n + 1元素，因为你在筛子期间用从 2 开始的数字索引这个数组。

此外，您应该为此数组使用unsigned char而不是bool，因为他键入bool可以大于 1 个字节。

这是一个修改版本：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
void SieveOfEratosthenes(unsigned long long m, unsigned long long n) {
unsigned char *prime = malloc(n + 1);
if (!prime) {
printf("FAILn");
return;
}
memset(prime, 1, n + 1);
unsigned long long i, j;
for (i = 2; i * i <= n; i++) {
if (prime[i]) {
for (j = i * 2; j <= n; j += i)
prime[j] = 0;
}
}
for (i = m; i <= n; i++) {
if (prime[i] && i != 1)
printf("%llun", i);
}
}
int main() {
clock_t begin, end;
unsigned long long int m, n;
if (scanf("%llu %llu", &m, &n) == 2) {
begin = clock();
SieveOfEratosthenes(m, n);
end = clock();
double time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
printf("nTime Taken : %f secsn", time_spent);
}
return 0;
}

可以为素候选者和筛切片使用单独的数组，对于非常大的数字切片是必需的。尝试为大小为ceil(sqrt(n + 1))的素候选者分配一个数组并在其上执行筛子，而不是为切片分配一个数组并使用第一个数组中的质数使用正确的偏移量和初始值在其上执行筛子。

这是一个幼稚的实现：

void SieveOfEratosthenes(unsigned long long m, unsigned long long n) {
unsigned int maxp = (unsigned int)(ceil(sqrt(n)) + 1);
unsigned char *composite = calloc(maxp, 1);
unsigned char *slice = calloc(n - m + 1, 1);
if (!composite || !slice) {
free(composite);
free(slice);
printf("FAILn");
return;
}
/* compute the primes */
unsigned int p, q;
for (p = 2; p * p < maxp; p++) {
if (!composite[p]) {
for (q = p * 2; q < maxp; q += p)
composite[p] = 1;
}
}
/* sieve the slice */
unsigned long long i;
if (m == 0)
slice[0] = 1;
if (m <= 1 && n >= 1)
slice[1 - m] = 1;
for (p = 2; p < maxp; p++) {
if (!composite[p]) {
i = 2 * p;
if (i < m) {
i = m - m % p;
if (i < m)
i += p;
}
while (i <= n) {
slice[i - m] = 1;
i += p;
}
}
}
for (i = m; i <= n; i++) {
if (!slice[i - m])
printf("%llun", i);
}
free(composite);
free(slice);
}