This code in C which decides if a number is a prime number crashes with large numbers. Why?

Question

So this is the code and it works perfectly fine till 4-5 digits.

int main()
{
int x;
printf("Enter a number: ");
scanf("%d", &x);
double list[x];
int i;
for(i=0;i<x;i++){
   list[ i ] = i+1;
}

double z;
int q;
double list2[x];
for(q=0;q<x;q++){
    z=x/list[q];
    if (z == floor(z)){
    list2[q] = z;
    }
    else {
        list2[q] = 0;
    }
}
printf("\n--------------\n");
int n;
double nulla = 0.00000000;
int zero = 0;
for(n = 0; n < x; n++)
{
    if (fabs(list2[n]-0.00)==0.00){
        zero++;
    }
}

if(zero == x-2){
printf("It is a prime number");
 }
else{
    printf("It is not a prime number");
}
printf("\n--------------\n");

return 0;
}

But if i input for example 987521. It just gives this message: Process returned -1073741571 (0xC00000FD) and I have been thinking that maybe an array cannot store such a large data, but maybe i am wrong. Any thoughts?

Your arrays `double list[x];` and `list2[x]` are probably overflowing the stack. — Steve Summit, Dec 20 '21 at 23:44
A good rule of thumb is that the stack is only 1MB. So any array that's bigger than 1MB can't be on the stack. A `double` is usually 8 bytes, so an array of 987521 doubles is about 8MB which is too big. — user3386109, Dec 20 '21 at 23:44
I replaced `double list[x];` with `double *list = malloc(x * sizeof(double));`, and likewise for `list2`, and the program "worked" for 987521 (also 987523). But this is not a very efficient way of testing for primality! (Also I got lucky: `malloc` didn't fail. Normally it's important to test for that.) — Steve Summit, Dec 20 '21 at 23:49
@SteveSummit Thanks! I know it is probably not the most efficent way but this is my first program and I just wanted to make something, could you give an example for a better approach? — Maxell, Dec 20 '21 at 23:52
@Maxell Nice job for your first try, then! The usual approach is to try factoring the number, using trial divisors of 2 and all the odd numbers up to the square root of the number you're testing. You don't need any big arrays. (Do a web search for "prime factorization algorithm" — I suspect you'll find millions of hits.) — Steve Summit, Dec 20 '21 at 23:54

vsoftco · Accepted Answer · 2021-12-20T23:51:36.147

0

Instead of allocating memory on the stack, as you do in the line

double list[x];

use dynamic allocation, like

double* list = malloc(x * sizeof(double));

Then, before the end of the program, don't forget to deallocate:

free(list);

The reason is that stack allocation is usually quite limited in size (order of MBs), and you'll overflow the stack once you allocate more than that limit. On the other had, dynamic memory (heap) is limited by the operating system, and can usually be quite large (limited by either the OS or the amount of total physical + virtual memory).

edited Dec 20 '21 at 23:51

answered Dec 20 '21 at 23:49

vsoftco

55,410
12
139
252

[Opinions differ](https://stackoverflow.com/questions/36584062) on whether it's "Don't forget to" or "If you really want to, you can". (Deallocate, that is.) – Steve Summit Dec 20 '21 at 23:51
1

@SteveSummit True :) But it's a good habit, especially when you `malloc` and `free` in the middle of the program... – vsoftco Dec 20 '21 at 23:52

This code in C which decides if a number is a prime number crashes with large numbers. Why?

1 Answers1