[C]Finding prime numbers - Crash when searching to many numbers

[GER_T4IGA]

I have a problem with a project for Uni. I know this has been done many times before and there is probably a more optimal way but I want to get there largely by myself.The problem currently is that if I set the scope(the program searches for prime numbers between 2- ... <-- this i called 'obergrenze'). if that upper boundry is set to roughly 1 million - haven't tried to many different values but 100k works - it crashes but idk why. Might this be a memory limitation? I have 4GB of VRAM but the program only uses about 30-35MB.

The task is to progrma something that finds all prime numnbers from 2- 100 000 000 and then trim for speed which i have not been able to do yet.

Some notes:

Sry for all the german variable names.

the 'int integer' is just a test and 100% irrelevant.

I first fill the array in which the position simbolizes the number - NOT its value - with -1 and then edit these to 1 for a prime number or 0 for non prime. In the end every number should be either 1 or 0. I separately count up how many primes i got and how many non for some controllability. Should work until there but it is for some reason not scalable.

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int main()
{
    //Sieb des Erathostines
    int obergrenze = 200000;
    int zahlen[obergrenze - 2 + 1];
    int i, j;
    int posAnzahl = 0, negAnzahl = 0, summe = 0;
    int integer = 2000000000;

    //array befüllen
    for(i = 0; i < obergrenze; i++)
    {
        zahlen[i] = -1;    
    }
    
    //Schleife vom niedrigsten bis zum höchsten sinnvollen Wert
    for(i = 2; i <= obergrenze; i++)
    {
        if(zahlen[i - 2] == -1 || zahlen[i - 2] != 0)
        {
            for(j = i; j <= obergrenze; j = j + i)
            {
                //printf("\n Kontrolle j=%d",j);
                if(j == i)
                {
                    zahlen[j - 2] = 1;
                    posAnzahl++; // eine Möglichkeit separat zu zählen    
                }else{ //if(zahlen[i]%j == 0)
                    if(zahlen[j - 2] == -1)
                    {
                    zahlen[j - 2] = 0;
                    negAnzahl++; // gehört zur Möglichkeit separat zu zählen und dient Kontrolle
                    }
                }
            }
            j = 0;
        }else{ //if(zahlen[i] == -1 || zahlen[i] != 0)
        }
    }
    
    printf("\n Anzahl der Primzahlen:%d\n Anzahl der NICHT-Primzahlen:%d\n Gesamtmenge der Zahlen %d gleich obergrenze: %d?",
    posAnzahl, negAnzahl + 1, posAnzahl + negAnzahl + 1, obergrenze);
    
    
    for( i = 0; i < obergrenze - 2 + 1; i++)
    {
        if(zahlen[i] == -1)
        {
            printf("\n Es wurden nicht alle Zahlen bearbeitet! zahlen[%d]", i + 2);
        }else{ //if(zahlen[i] == -1)
            summe = zahlen[i] + summe;
        }
    }
    
 return(8);
}

 

EDIT:

To be clear please don't suggest me just copying something else. I would very much prefere to find out and solve what the problem is I have right here.

The maximum value the program works with is obergrenze=518132;

[slightlyjaded]

Okay it's been awhile since I've done this shit (I'm a chef by trade) Aren't integers limited by memory, I'd start with a float instead.

[GER_T4IGA]

4 minutes ago, slightlyjaded said:

Okay it's been awhile since I've done this shit (I'm a chef by trade) Aren't integers limited by memory, I'd start with a float instead.

supposedly a signed int can range from +/-2billion. That should be enough for the 100 000 000 we are supposed to program for.

[slightlyjaded]

Just now, GER_T4IGA said:

supposedly a signed int can range from +/-2billion. That should be enough for the 100 000 000 we are supposed to program for.

Merely mentioned as you were worried about ram, integers are processed differently to floats (closer to scientific notation for computers)

[TheHoijf]

Why not go on stackoverflow? You're probably having exactly that as a problem as well. Your array is only allowed to store so much data before capping out.

Maybe?

[GER_T4IGA]

12 minutes ago, TheHoijf said:

Why not go on stackoverflow? You're probably having exactly that as a problem as well. Your array is only allowed to store so much data before capping out.

Maybe?

Do you know how I would fix that?

[TheHoijf]

Run it and send me the error message please. It'll give me some much needed insight.

[GER_T4IGA]

7 minutes ago, TheHoijf said:

Run it and send me the error message please. It'll give me some much needed insight.

Normal "Windows: Program stopped responding" message.

[TheHoijf]

Nothing from VisualStudio?

[GER_T4IGA]

Just now, TheHoijf said:

Nothing from VisualStudio?

I am using Dev-C++ as per what my prof recommended and what we use in class.

[TheHoijf]

I don't have anything to run the program from my end. Its probably got errors but I commented where I made changes so you can just check those parts.

int main()
{
    //Sieb des Erathostines
    int size = 200000;
    int array[size]; //Changed
    int i, j;
    int posNumber = 0, negNumber = 0, sum = 0;
    //Removed here
    for(i = 0; i < size; i++) //Changed
    {
        array[i] = -1;    
    }

    for(i = 2; i < size; i++) // Changed
    {
        if(array[i - 2] == -1 || array[i - 2] != 0)
        {
            for(j = i; j < size; j = j + i) // << this is adding I, then I+I, then I+I+I and may be causing the issue?
            {
                if(j == i && j < size) // << changed this
                {
                    array[j - 2] = 1;
                    posNumber++;  
                }else{
                    if(array[j - 2] == -1)
                    {
                    array[j - 2] = 0;
                    negNumber++;
                    }
                }
            }
            j = 0;
        }
    }
    
    printf("\n Anzahl der Primarray:%d\n Anzahl der NICHT-Primarray:%d\n Gesamtmenge der array %d gleich size: %d?",
    posNumber, negNumber + 1, posNumber + negNumber + 1, size);
    
    
    for( i = 0; i < size; i++)
    {
        if(array[i] == -1)
        {
            printf("\n Es wurden nicht alle array bearbeitet! array[%d]", i + 2);
        }else{ //if(array[i] == -1)
            sum = array[i] + sum;
        }
    }
    
 return(8);
}

 

[TheHoijf]

I also advise using VisualStudio. Its what I used to use and its amazing.

[GER_T4IGA]

3 minutes ago, TheHoijf said:

I also advise using VisualStudio. Its what I used to use and its amazing.

I will probably move on from DevC++ but for now i will stay with what is recommended to me.

Thei, i+i, i+i+i ... is intended. at i=2 it edits all the numbers divisable by 2, then i=3 all divisable by 3 and so on. That is the way we are supposed to do it.

I had a lsot of mistakes in previous version but I can confirm that up until the sample size it crashes at the results are correct and the program is ... well working fine.

[GER_T4IGA]

8 minutes ago, TheHoijf said:

if(j == i && j < size) // << changed this

this also shouldn't be necessary as the for loop above it has exactly that as its runtime condition.

[TheHoijf]

Sorry  then. I don't have anything to run it on and fix it but you can just comment lines out and see if it runs. One line at a time and once it runs you've found your mistake. You can then trace it back and fix it. If you or someone haven't resolved the issue by the time I have VisualStudio I'll send you my solution.

GL

[Issun]

You are allocating the array on the stack:

http://softwareengineering.stackexchange.com/questions/310658/how-much-stack-usage-is-too-much

Reducing the array size got rid of the "Program.exe has stopped working" for me.

Try using malloc (and free) instead.

 

[Unimportant]

14 minutes ago, Issun said:

You are allocating the array on the stack:

http://softwareengineering.stackexchange.com/questions/310658/how-much-stack-usage-is-too-much

Reducing the array size got rid of the "Program.exe has stopped working" for me.

Try using malloc (and free) instead.

 

You beat me to it by a minute

 

This line is the problem:

int zahlen[obergrenze - 2 + 1];

The stack can't hold an array that large. (When obergrenze is too large, for low values there is no problem).

To fix this, dynamically allocate the memory:

int *zahlen = malloc(sizeof(int) * (obergrenze - 2 + 1));

Do not forget to free the memory if you no longer need it using free();

 

[Issun]

5 minutes ago, Unimportant said:

You beat me to it by a minute

 

This line is the problem:

int zahlen[obergrenze - 2 + 1];

The stack can't hold an array that large. (When obergrenze is too large, for low values there is no problem).

To fix this, dynamically allocate the memory:

 

std::unique_ptr<int[]> zahlen(new int[obergrenze - 2 + 1]);

You need to include header "memory" for std::unique_ptr.

This allocates the memory dynamically with new and immediately hands the pointer to std::unique_ptr to manage. (RAII).

You will need to modify the rest of your program because you are now no longer dealing with a int array but with a smart pointer.

 

C++14 further improves upon this with std::make_unique, allowing removal of the explicit new call, but not all compilers support this yet.

He tagged the post with "C" though, so using malloc and free should solve his problem without changing much.

[Unimportant]

I noticed too late, already fixed.

[Nineshadow]

Yeah, you're allocating too much on the stack and that throws an error.

You could instead use dynamic allocation to store the array on the heap.

 

Another thing that could maybe make things just a little bit better is to use the _Bool data type (since C99) for the array instead of int, since it's smaller. Of course, you wouldn't be able to use -1 then. But I'm pretty sure you're using a Sieve of Eratosthenes, and for that a boolean array will do just fine. Something like this:

#include <stdio.h>
#define N 100000000
_Bool v[N];
int main()
{
    memset(v+2,1,N-2);
    for(int i=3;i<=N;i+=2)
        if(v[i])
            for(int k=2;k*i<=N;++k)
                v[k*i]=0;
    return 0;
}

And with dynamic allocation:

#include <stdio.h>
#define N 100000000
_Bool *v;
int main()
{
    v=(_Bool*)malloc(N);
    memset(v+2,1,N-2);
    for(unsigned long i=3;i<=N;i+=2)
        if(v[i])
            for(unsigned long k=2;k*i<=N;++k)
                v[k*i]=0;
    return 0;
}

 

[mathijs727]

But just to be clear:

Its almost impossible to write a program (or for us to help you), if you refuse to use a debugger.

Even if you dont want to use Visual Studio, there is probably a way to get debugging working with your editor/IDE (like a standalone debugger such as GDB).

[GER_T4IGA]

14 hours ago, mathijs727 said:

But just to be clear:

Its almost impossible to write a program (or for us to help you), if you refuse to use a debugger.

Even if you dont want to use Visual Studio, there is probably a way to get debugging working with your editor/IDE (like a standalone debugger such as GDB).

I have used the debugger to get the thing working to the point where everything is up and running except the dynamic search range and that I can't fix with the debugger and DevC++ doesn't throw any errors so this was all I got.

Am i misundertsanding something about the debugger here?

[GER_T4IGA]

23 hours ago, Unimportant said:

 

To fix this, dynamically allocate the memory:

int *zahlen = malloc(sizeof(int) * (obergrenze - 2 + 1));

 

What exactly does this do? I read up malloc on the reference and understood it but I don't understand what the purpose of the typecast and the sizeof is right here.

[Unimportant]

1 hour ago, GER_T4IGA said:

What exactly does this do? I read up malloc on the reference and understood it but I don't understand what the purpose of the typecast and the sizeof is right here.

There is no explicit typecast, only the `sizeof` operator.

The parameter passed to `malloc` is a `size_t` that takes the amount of memory to allocate, in bytes.

Since we want to allocate memory for `x` amount of integers, where `x = obergrenze - 2 + 1`, we first need to know how many bytes long a integer is. This is done with:

sizeof(int)

The result is then multiplied with `x`:

sizeof(int) * x
//Which, when we substitute x,becomes:
sizeof(int) * (obergrenze - 2 + 1)

EDIT:

You might've gotten the typecast from:

int *zahlen = malloc...etc

This is not a explicit typecast, it simply declares a integer pointer called `zahlen` to which the result of `malloc` (a pointer to the allocated block of memory) is assigned. `malloc` returns a pointer of type `void*` which is implicitly converted to `int*` in C!

 

However, when you compile with a C++ compiler you will need to add a explicit cast, contrary to what many ppl think C and C++ have many differences, this is one of them.

//To compile with a C++ compiler...
int *zahlen = (int *) malloc(sizeof(int) * (obergrenze - 2 + 1));

//However, if you're learning C, you should really find a C compiler 
//and not compile your C code with a C++ compiler.
//In C++ you should not use malloc altogether.

 

You should also test if the allocation was successful. `malloc` returns a null pointer when allocation fails, so you should add something like this:

int *zahlen = malloc(sizeof(int) * (obergrenze - 2 + 1));
if (!zahlen)
{
  	//Handle failure of memory allocation here... 
}

 

[mathijs727]

21 hours ago, GER_T4IGA said:

I have used the debugger to get the thing working to the point where everything is up and running except the dynamic search range and that I can't fix with the debugger and DevC++ doesn't throw any errors so this was all I got.

Am i misundertsanding something about the debugger here?

Because a debugger would tell you what is going on.

I've personally experienced the same thing with Visual Studio and it explicitely told me I was running out of stack memory.