C Programm unter Windows lauffähig machen

[Beitrag]

Hallo Leute,

ein Kommilitone hat ein kleines C-Programm für Primzahlen geschrieben.
Wir wollten mal gucken, wie lange es auf meinem System dauert, bis es fertig ist. Also hat er mir den Quellcode geschickt und ich hab's bei mir unter Win 10 compiliert (MinGW). Allerdings ist es nach allerspätestens einer Minute abgestürzt und hat nichts berechnet.
Ich hab dann das Linux-Subsystem von Windows aktiviert und lasse es gerade darüber laufen - funktioniert einwandfrei.

Mich würde jetzt interessieren, was hier die Probleme macht und wie man es plattformübergreifend lauffähig machen könnte.
Ach und bitte möglichst einfach erklären. Meine Kentnisse in C und Linux sind rudimentär.

#include <time.h>
#include <stdio.h>

/*Aufgabe 4*/
void primes(void)
{
	int start_time;
	int end_time;
	int primes[1999999];	/*Feld, um Primzahlen zu speichern*/
	int n;	/*n ist eine Zahl*/
	int count;	/*Anzahl der bisher gefundenen Primzahlen*/
	int isprime;	/*variable, die den Status einer Zahl (Prim bzw. nicht Prim) speichert*/
	int t;	/*Laufvariable für primes*/
	int z;	/*Laufvariable für die Ausgabe der Primzahlen*/

	start_time = clock()/CLOCKS_PER_SEC;
	primes[0]=2;/*die erste Primzahl ist die 2*/
	/*jede Zahl n untersuchen*/
	for(n=3,count=1; count<2000000; ++n)
	{
		isprime=1;	/*ich gehe davon aus, dass n eine primzahl ist*/
		/*n durch jede bisher gefundene Primzahl versuchen zu teilen*/
		for(t=0; t<count; ++t)
		{
			if(n % primes[t] == 0) {
				isprime = 0;	/*n kann keine Primzahl sein, also isprime entsprechend setzen*/
				break;
			}
		}

		/*falls isprime hier immer noch 1 ist, ist n eine Primzahl*/
		if(isprime) {
			if( (count+1)%10000 == 0) printf("Found the %d. prime number...\n", count+1);
			primes[count++]=n;	/*NACHDEM n in primes gespeichert wird, wird count inkrementiert*/
		}
	}
	end_time = clock()/CLOCKS_PER_SEC;

	/*Ausgabe der Primzahlen*/
	for(z=0; z<count; ++z) {
		printf("Die %d. Primzahl lautet: %d\n", z+1, primes[z]);
	}
	printf("Calculation time: %d seconds.\n", end_time-start_time);
}

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

Danke.

 

[DaZpoon]

Da kann man erstmal nur orakeln. Gibt es schon irgendwelche Ausgaben vom Programm?

int primes[1999999];

Vielleicht ist das zu groß für den Stack? Versuche den Speicher mal dynamisch per malloc zu allocieren (und mit free wieder freizugeben).

 

[maxwell-cs]

Lass es doch mal unter Linux in valgrind laufen, eventuell zeigt das schon den/die Fehler.
Auf den ersten Blick faellt schonmal auf, dass count zu groß werden kann:

int primes[1999999];

vs

for(n=3,count=1; count<2000000; ++n)

 

[Hancock]

Unter MSVC gibt's nen stack-Overflow.

​Linux wird das nicht so genau prüfen, gab genau deswegen mal ne Reihe an Sicherheitslücken.

Die Stack-Größe ist laut https://msdn.microsoft.com/de-de/library/windows/desktop/ms686774(v=vs.85).aspx 1 MB, daher sind 2M int's ein kleiner Faktor zu groß => malloc.

​EDIT:
Hier dein Programm angepasst, braucht nur noch 3,7 s auf meinem PC (MSVC, 64 bit, Release).

#include <time.h>
#include <stdio.h>
#include <cmath>

/*Aufgabe 4*/
void primes(void)
{
 double start_time;
 double end_time;
 int *primes=new int[2000000]; /*Feld, um Primzahlen zu speichern*/
 int n; /*n ist eine Zahl*/
 int count; /*Anzahl der bisher gefundenen Primzahlen*/
 int isprime; /*variable, die den Status einer Zahl (Prim bzw. nicht Prim) speichert*/
 int t; /*Laufvariable für primes*/
 int z; /*Laufvariable für die Ausgabe der Primzahlen*/
 start_time = clock() *1.0/ CLOCKS_PER_SEC;
 primes[0] = 2;/*die erste Primzahl ist die 2*/
      /*jede Zahl n untersuchen*/
 for (n = 3, count = 1; count<2000000; ++n)
 {
  isprime = 1; /*ich gehe davon aus, dass n eine primzahl ist*/
      /*n durch jede bisher gefundene Primzahl versuchen zu teilen*/
  int limit = (int)sqrt(n);
  for (t = 0; t<count; ++t)
  {
   if (primes[t] > limit)
    break;
   if (n % primes[t] == 0) {
    isprime = 0; /*n kann keine Primzahl sein, also isprime entsprechend setzen*/
    break;
   }
  }
  /*falls isprime hier immer noch 1 ist, ist n eine Primzahl*/
  if (isprime) {
   //if ((count + 1) % 10000 == 0) printf("Found the %d. prime number...\n", count + 1);
   primes[count++] = n; /*NACHDEM n in primes gespeichert wird, wird count inkrementiert*/
  }
 }
 end_time = clock() *1.0/ CLOCKS_PER_SEC;
 /*Ausgabe der Primzahlen*/
 for (z = 0; z<count; ++z) {
  printf("Die %d. Primzahl lautet: %d\n", z + 1, primes[z]);
 }
 printf("Calculation time: %f seconds.\n", end_time - start_time);
 delete[]primes;
}
int main(void)
{
 primes();
 return 0;
}

​

​Achtung: ist C++ (nicht C).

 

[hans_meiser]

Ja, das wird ein stack overflow. Je nach Compiler kannst du die Stackgroesse aendern, aber ich wuerde davon abraten, schlechter Stil.

Die schnellste Loesung ist, das 'primes' array global zu machen, es also ausserhalb der Funktion zu deklarieren. Dann geht es naemlich auf den heap, nicht auf den stack. Dafuer musst du allerdings auch die Variable umbenennen, damit sie nicht denselben Namen hat wie die Funktion.

Z.B.

int pNumbers[1999999]; /*Feld, um Primzahlen zu speichern*/

/*Aufgabe 4*/
void primes(void)
...

(und dann natuerlich auch die Variable in der Funktion umbenennen.)


Natuerlich sind globale variablen auch kein feiner Stil. Eine dynamische Allozierung des arrays via malloc() und am Ende free() ist angebrachter.

 

[Beitrag]

Danke für die Antworten, werde das morgen mal testen.

Ist inzwischen übrigens durchgelaufen: 4615 Sekunden, also 1:16:55.

@Hancock 3,7s hören sich für mich da wie Magie an.

 

[Hancock]

Du musst nur bis zur Wurzel testen, dadurch wird es deutlich schneller. Du sparst dir damit (1-sqrt(n)/n)*100 % der Vergleiche, nachdem sqrt(n)/n) -> 0 sparst du dir immer mehr Vergleiche für größere n und hast dadurch statt einer O(n^2,...) oder so eine O(n^1,...) Funktion.

​Wichtige Lektion: Ist der Algorithmus scheiße, beißen dich die Hunde.

 

[maxwell-cs]

O(n^1.5)

 

[aroxx]

Natuerlich sind globale variablen auch kein feiner Stil. Eine dynamische Allozierung des arrays via malloc() und am Ende free() ist angebrachter.

kannst du das bitte rot markieren?

 

[RalphS]

--