我如何在c中创建一个有很多地方的数组?

Question

我正在用c编写橡皮擦筛。我以前用其他语言编程过，但我从未遇到过这个问题。下面是我的算法:

#include <stdio.h>
#include <stdbool.h> 
#include <math.h>
#include <time.h>  
#include <limits.h>   

int main(){
clock_t t;
t = clock();
int n = 1299710;

bool pPrimes[n];

for(int i = 0; i<n; i++){
pPrimes[i] = true;
}

pPrimes[0] = false;
pPrimes[1] = false;
for(int i = 2; i<sqrt(n); i++){
if(pPrimes[i]){
for(int x = i*i; x<n; x+=i){
pPrimes[x] = false;
}
}
}
for(int i = 2; i<n; i++){
if (pPrimes[i]){
printf("%dn", i);
}
}
t = clock() - t;
double time_taken = ((double)t)/CLOCKS_PER_SEC;

printf("%f", time_taken);
return 0;
}

当我声明pPrimes时，n不能足够大。100万左右就行了，但不能更多。有办法解决这个问题吗?

我试着调试，但我只得到这个错误信息:

line 1: 4320 Segmentation fault: 11

Answer 1

一些问题:

本地空间不足

OP报告n大，有问题。最好使用malloc()来分配。

bool不一定是最窄的类型-使用unsigned char。最好分配一个无符号大小，如unsigned或size_t。

//int n = 1299710;
//bool pPrimes[n];
unsigned n = 1299710;
if (n < 2) {  // Avoid edge cases
fprintf(stderr, "Use larger value, not %un", n);
return EXIT_FAILURE;
}
unsigned char *pPrimes = malloc(sizeof *nPrimes * n);
if (pPrimes == NULL) {
fprintf(stderr, "Out-of-memory %un", n);
return EXIT_FAILURE;
}

关闭一个

我希望int n = 1299710;意味着找到所有到的质数，包括n。

unsigned char *pPrimes = malloc(sizeof *nPrimes * (n+1));
// for(int i = 2; i<n; i++){
for(unsigned i = 2; i <= n; i++){  // <=

引用这个伪代码，边缘测试差1。
对于整数问题，不要信任原始sqrt()。当预期结果为x.00000时…，该函数可能返回x_minus_1.99999....

unsigned qsrt_n = lround(sqrt(n));
// for(int i = 2; i<sqrt(n); i++){
for(unsigned i = 2; i <= sqrt_n; i++){  // <=
if(pPrimes[i]){
// for(int x = i*i; x<n; x+=i){
for(unsigned x = i*i; x <= n; x+=i){  // <=
pPrimes[x] = false;
}
}
}

Answer 2

您在堆栈中分配了太多内存。这被称为堆栈溢出。

要么(正如@Gerhardh在评论中所说):

1. 使用static数组
2. 使用全局数组
3. 使用malloc()

---

1。与static数组:

int main(void)
{
#define n 1299710
static bool primes[n] = {false, false};
for (size_t i = 2; i < n; ++i) {
primes[i] = true;
}

long srn = sqrt(n) + 1;

for (size_t i = 0; i < srn; ++i) {
if (!primes[i]) continue;

for (size_t ii = i*i; ii < n; ii += i)
primes[ii] = false;
}
// print...
}

---

2。使用全局数组:

#define n 1299710
/*static?*/ bool primes[n] = {false, false};
int main(void)
{
for (size_t i = 2; i < n; ++i) {
primes[i] = true;
}
long srn = sqrt(n) + 1;
for (size_t i = 0; i < srn; ++i) {
if (!primes[i]) continue;

for (size_t ii = i*i; ii < n; ii += i)
primes[ii] = false;
}

// print...
}

---

3。使用动态数组:

int main(void)
{
const size_t n = 1299710;
bool *primes = malloc(n * sizeof bool);

if (!primes) {
printf("Memory issues. Goodbye!n");
return EXIT_FAILURE;
}

for (size_t i = 2; i < n; ++i) {
primes[i] = true;
}

primes[0] = false;
primes[1] = false;
long srn = n == 1 ? 1 : sqrt(n) + 1;
for (size_t i = 0; i < srn; ++i) {
if (!primes[i]) continue;

for (size_t ii = i*i; ii < n; ii += i)
primes[ii] = false;
}

// print...
}