I'm making the sieve of erasthostenes in c. I have programmed it in other languages before but I never encountered this problem. Here's my algorithm:

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

It's when I declare pPrimes that n can't be large enough. A million or so works but not more. Is there anyway of fixing this?

I tried debugging but I only get this error message:

line 1: 4320 Segmentation fault: 11

CodePudding user response：

Some issues:

Out of local space

OP reports with large n, there is trouble. Better to allocate with malloc().

bool is not certainly the narrowest type - use unsigned char. Better to allocate with an unsigned size such as unsigned or size_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;
 }

Off by one

I would expect int n = 1299710; to imply finding all the primes up to and including n.

unsigned char *pPrimes = malloc(sizeof *nPrimes * (n 1));

// for(int i = 2; i<n; i  ){
for(unsigned i = 2; i <= n; i  ){  // <=

Referencing this pseudocode, edge tests are off by one.
Do not trust a raw sqrt() for an integer problem. When the expected result is x.00000..., that function may return 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;
        }
    }
}

CodePudding user response：

You are allocating too much memory in the stack. This is known as a stack overflow.

Either (as @Gerhardh said in a comment):

1. Use a static array
2. Use a global array
3. Use malloc()

1. With a static array:

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. With a global array:

#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. With a dynamic array:

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