如何在 C 中制作一个有很多位置的数组？-解网

问：

我正在制作 c 中 erasthostenes 的筛子。我以前用其他语言编程过，但我从未遇到过这个问题。这是我的算法：

#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("%d\n", i);
        }
    }
    t = clock() - t;
    double time_taken = ((double)t)/CLOCKS_PER_SEC;
 
    printf("%f", time_taken);

    return 0;
}

这是我宣布这还不够大的时候。大约有一百万个工作，但不会更多。有没有办法解决这个问题？pPrimesn

我尝试调试，但我只收到以下错误消息：

第 1 行：4320 分段故障：11

C 筛

堆栈内存是有限的资源。将如此大的数组放在堆栈上可能会溢出：。由于您具有硬编码大小，因此不需要 VLA，但可以使其成为该函数中的静态数组。或者将其移出函数并使其成为全局函数。或者，您可以使用动态内存分配。bool pPrimes[n];

1赞 Gerhardh 12/20/2022

你应该看看埃拉托色尼的筛子。你只需要一个数组来表示你想要找到的素数，而不是所有的数字，直到最大的素数。

1赞 Gerhardh 12/20/2022

你通过成为一个 constand 表达式，而不是一个变量来制作它。为了解决“没有意义”的问题，您可以阅读任何 C 教程或教科书，并查看有关局部变量的部分。或搜索“静态变量”等。static bool pPrimes[SIZE];SIZE

1赞 Gerhardh 12/20/2022

你做或其他一些大数字。但正如我所提到的：如果你实现了这种筛子算法，你就不需要像你目前的方法那样大的数组，因为你不需要存储非素数。#define SIZE 1299710

1赞 Gerhardh 12/20/2022

@Yunnosch OP 似乎不想检查是否是素数，而是要找到所有素数。nn

答：

0赞 chux - Reinstate Monica 12/20/2022 #1

一些问题：

本地空间不足

OP报告大，有麻烦。最好使用 .nmalloc()

bool肯定不是最窄的类型 - 使用 .最好使用无符号大小（如或）进行分配。unsigned charunsignedsize_t

 //int n = 1299710;
 //bool pPrimes[n];

 unsigned n = 1299710;

 if (n < 2) {  // Avoid edge cases
   fprintf(stderr, "Use larger value, not %u\n", n);
   return EXIT_FAILURE;
 }

 unsigned char *pPrimes = malloc(sizeof *nPrimes * n);
 if (pPrimes == NULL) {
   fprintf(stderr, "Out-of-memory %u\n", 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。
不要相信原始数据的整数问题。当预期结果为 x.00000...时，该函数可能会返回 x_minus_1.99999...。sqrt()

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

0赞 Zakk 12/20/2022 #2

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

要么（正如@Gerhardh在评论中所说）：

使用数组static
使用全局数组
用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...
}

如何在 C 中制作一个有很多位置的数组？

how do i make a array with lots of places in c?

评论

1. 使用数组：static

2. 使用全局数组：

3. 使用动态数组：

评论

1. 使用数组：`static`