Prime generator using a huge array in C

Question

I'm trying to make a prime number generator using arrays. I started with a 1D array but the max limit on my computer was 250000. So I thought maybe I should make a 2d or more array to go to the next line once this limit is reached to avoid problems on my PC. But I have no idea how to do it. Any help would be welcome.

#include<stdio.h>
#include<math.h>
#include<stdbool.h>
#include<time.h>
#define LIMIT 250000ul

//prime number generator using arrays 

void prime_generator(){

    unsigned long long n; 
    printf("How many primes do you want generated : "); 
    scanf("%llu", &n);

    unsigned long long p[LIMIT];  
    unsigned long long i, j=2; 
    unsigned long long num; 
    bool isPrime; 

    unsigned long long primes_per_line, space_column; 
    printf("How many primes do you want displayed per line? : "); 
    scanf("%llu", &primes_per_line); 
    printf("Enter space : "); 
    scanf("%llu", &space_column); 

    p[0]=2, p[1]=3;//first two primes
    unsigned long long count = 2; 

    clock_t begin = clock();   
    for(num = 5;count < n; num=num+2){//only test for odd number 
        isPrime = true; 
        for(i = 1;i < j && p[i] <= sqrt(num) ;i++){
            if(num%p[i]==0){
                isPrime = false;  
                break;//break out of i loop 
            }
        }
        if(isPrime == true){
            ++count; 
            p[j] = num; //new prime found 
            ++j; 
        }
    }
    clock_t end = clock(); 
    double time_spent = (double) (end-begin)/CLOCKS_PER_SEC; 

    for(i = 0; i < n; i++){
        if(i!=0 && i % primes_per_line == 0) printf("\n"); 
        printf("%*llu", space_column, p[i]); 
    }

    printf("\nCrunching time is : %.12f", time_spent);
}

int main(void){
    prime_generator(); 
    return 0; 
}

Changing the dimension of the array doesn't increase the amount of memory you have available to you. — lurker, Jun 06 '17 at 00:15
A 2D array is not going to take less memory than a 1D array. Look into using dynamic memory instead - ie, call `malloc`. Better still, improve your algorithm to not need so much memory. — kaylum, Jun 06 '17 at 00:16
If your compiler does not "see inside" `sqrt(num)`, then that function will be repetitively called - unnecessarily. Suggest `unsigned long long limit = llrint(sqrt(num)); for(i = 1;i < j && p[i] <= limit;i++){ ...` — chux - Reinstate Monica, Jun 06 '17 at 01:27

Basile Starynkevitch · Accepted Answer · 2017-06-06T01:16:31.970

Your unsigned long long p[LIMIT]; is a local variable (with automatic storage duration) inside your prime_generator function, so it is on the call stack (which is often limited to one or a few megabytes). Declare it as a static or make it a global variable (in both cases, it gets a static storage duration). Then it could be much larger, but your prime_generator won't be re-entrant anymore (but in your case, you don't care).

Declaring an array as multi-dimensional won't improve its memory size (so won't solve the problem of an excessive call frame size of a variable declared local).

Better yet, use C dynamic memory allocation that is calloc (don't forget to test it against failure, when it returns NULL use perror then exit) and free; beware of memory leaks; tools like valgrind could be helpful. With calloc (or malloc) you'll then grow your virtual address space and be limited by machine and system resources (probably gigabytes).

Avoid buffer overflows. See this.

Read also wikipages on prime numbers and on primality tests. There are more efficient algorithms.

You should be able to compute a million primes (ending with 15485761 15485773 15485783 15485801 15485807 15485837 15485843 15485849 15485857 15485863) in a few seconds at most (and probably in less than half a second).

Prime generator using a huge array in C

1 Answers1