C Schleifenproblem

[Darlis]

IDEs bieten meist eine Auto-Formatierung an, die den gesamten Code nach einem bestimmten Standard formatiert. Entweder per (Kontext-)Menü und/oder Tastenkombi.

Manuelle Einrückung: [Tab] schiebt nach rechts, [Shift]+[Tab] nach links.

 

[Hancock]

Also Z. 57: Das kann nicht gut gehen (und ist so nicht sinnvoll), zuerst schreibst du an irgendeine Speicherposition (0x0000, da C alle globalen Variablen auf 0 initialisiert). Dann erst forderst du Speicher dafür an, vertausch einfach Z. 57 mit Z. 58.

Bei deinem Auskommentierten Code von ist_primzahl: Da machst du es deutlich zu kompliziert.
i prim = i%z!=0 für alle {z|z Primzahl}
<=> | z%z = i für alle z>i
i prim, wenn i%z!=0 für alle {z|z Primzahl und z<i }
=>
i nicht prim, wenn i%z==0 für mindestens ein z, z prim
=>
i nicht prim, wenn i%z==0 für mindestens ein z, z prim und z<i
=>
für jedes Element in primzahlen{
falls i%Element==0{
i nicht prim => return false;
}
}
i prim
=> i muss Element von primzahlen werden.
return true;

Ach und guck, dass du potPrimzahl initialisierst oder einfach stattdessen zahl schreibst.

 

[datalukas]

@Hancock Ja, das mit der Initialisierung war ein unbedachter Fehler, aber beim zweiten verstehe ich dich zwar, aber ich weiß nicht, was ich da jetzt ändern soll, denn eigentlich prüfe ich nach dem Schema.

bool ist_primzahl(long long zahl)
{
  int potPrimzahl, x;
  int i = 0;
  while(primzahlen[i] <= sqrt((double)zahl) + 1)
  {
	 if(zahl%primzahlen[i]==0)
		 return false;
	 if(i<anzahlPrimfelder-1)
		i++;
	 else
	 {
		x = 0;
		potPrimzahl=primzahlen[i] + 2;
		while(primzahlen[x] <= sqrt((double)potPrimzahl))
		{
			if(potPrimzahl%primzahlen[x]==0)
			{
				potPrimzahl+=2;
				x = -1;
			}
			x++;
		}
		primzahlen[i]= potPrimzahl;
		anzahlPrimfelder++;
		i++;
	 }
  }
  return true;

Nur beim Herausfinden von neuen Primzahlen muss es etwas anders gehen, denn hier kann ich ja nicht einfach return false machen.
@Darlis Danke, wusste nur nicht, Tab kannte ich natürlich schon, aber noch nicht für den ganzen Block.

 

[Hancock]

Also z.B:
Z5:
Warum bis sqrt(zahl) gehen, du weißt, weil du in Mathe gut bist, dass nur die Primzahlen, die du bisher gefunden hast, ein Teiler sein können. Also wozu die Wurzel, mach doch for(int i=0;i<prinzahlenAnzahl;++i)
Z. 13 ff:
Das sieht für mich aus, als würdest du nochmal alles testen und zwar für eine andere Zahl. Warum? die Funktion heist ist_primzahl und nicht finde_naechste_primzahl, vor allem, wenn du diese dann nicht zurückgibst.
Z. 20: Hässlich
Z. 24: Du überschreibst eine bereits gefundene Primzahl mit einer Zahl, die möglicherweise gar nicht prim ist
Der Algo, den du geschrieben hast, hat O(n²) und ist daher seehr langsam, wenn nicht sogar falsch.

merk dir: Wenn es ein Teiler gibt, dann hast du den schon vorher in primzahlen abgespeichert, nutz die Information entsprechend.

 

[datalukas]

Ich glaube, ich habe noch nicht genau erklärt, wie ich das eigentlich machen will. Die Schleife läuft bis zur Wurzel von zahl, und falls dann nicht genügend Primzahlen zur Verfügung stehen, wird (Z11 - 23) eine neue gefunden. Das Ergebnis wird dann im nächsten Feld von primzahlen abgespeichert, damit es auch später noch genutzt werden kann. Gleichzeitig wird anzahlPrimzahlen hochgesetzt, damit man weiß, wieviele Felder schon mit Primzahlen belegt sind.

Allerdings ist bei Z24 ein Fehler unterlaufen, richtig wäre:

primzahlen[i+1]= potPrimzahl;

 

[Hancock]

Du willst also immer alle Primzahlen bis wurzel(zahl) im Speicher halten, OK, das geht natürlich auch.
Wobei ich sagen muss, die innere Schleife ist ganz schön clever, weil sie eigentlich gleich zwei Schleifen verwurschtelt.

 

[datalukas]

#include "stdafx.h"
#include <stdlib.h>
#include <math.h> 
int *primzahlen;
int anzahlPrimfelder = 2;
bool ist_primzahl(long long zahl)
{
	  int potPrimzahl, x;
	  int i = 0;
	  while(primzahlen[i] <= sqrt((double)zahl) + 1)
	  {
		 if(zahl%primzahlen[i]==0)
			 return false;
		 if(i<anzahlPrimfelder-1)
			i++;
		 else
		 {
			x = 0;
			potPrimzahl=primzahlen[i] + 2;
			while(primzahlen[x] <= sqrt((double)potPrimzahl))
			{
				if(potPrimzahl%primzahlen[x]==0)
					potPrimzahl+=2;
				else
					x++;
			}
			primzahlen[i+1]= potPrimzahl;
			anzahlPrimfelder++;
			i++;
		 }
	 }
}	
int main(void)
{
	int test;
	long long summe = 2;
	long long i = 3;
	primzahlen = (int *) malloc(1000000*sizeof(long long));
	primzahlen[0] = 2;
	primzahlen[1] = 3;
	while(i < 2000000)
	{
		if(ist_primzahl(i) == true)
			summe += i;
		i+=2;
		printf("%lld und %lld\n", i, summe);
	}
	scanf("%i", &test);
	return 0;
}

So, jetzt hab ichs.

Der Fehler lag darin, dass die allein gespeicherte Primzahl am Anfang ja 2 war. Deswegen nahm er als potPrimzahl nur gerade Werte (Z19). Ich musste dann nur noch eine zweite einfügen. Könnte ich hier eigentlich diese beiden Zeilen eigentlich irgendwie verkürzen mittels einer Art Liste?

primzahlen[0] = 2;
primzahlen[1] = 3;

Du hast mal sowas in der Art geschrieben, allerdings war hier auch ein Array mit fester Anzahl vorhanden:

int primzahlen[1000]={2};

 

[maxwell-cs]

der code enthält noch 2 fehler:
1.: ist_primzahl gibt nichts zurück, falls das ende der funktion in zeile 32 erreicht wird. da sollte ein "return true" hin. sollte der compiler eigentlich auch anmerken.

2.: mit obiger änderung erkennt ist_primzahl zwar primzahlen korrekt, allerdings gilt nicht die invariante, die zumindest die variablenbenennung suggeriert, dass im array primzahlen auch wirlklich nur primzahlen enthalten sind.
um das zu erreichen, musst du in zeile 23 (nummerierung deines codes) zusätzlich noch x auf 1 setzen, sonst werden kleine teiler beim nächsten kandidaten nicht erkannt.
beispiel: bei potprimzahl == 25 wird der teiler 5 gefunden, potprimzahl auf 27 erhöht und dann teiler ab 5 getestet und somit 27 als primzahl erkannt.

 bool ist_primzahl(long long zahl)
 {
    int potPrimzahl, x;
    int i = 0;
    while(primzahlen[i] <= sqrt((double)zahl) + 1)
    {
       if(zahl%primzahlen[i]==0) {
          return false;
       }
       if(i<anzahlPrimfelder-1) {
          i++;
       }
       else  {
          x = 0;
          potPrimzahl=primzahlen[i] + 2;
          while(primzahlen[x] <= sqrt((double)potPrimzahl))
             {
             if(potPrimzahl%primzahlen[x]==0) {
                potPrimzahl += 2;
                x = 1;
             }
             else {
                ++x;
             }
          }
          primzahlen[i+1]= potPrimzahl;
          anzahlPrimfelder++;
          i++;
       }
    }
    return true;
 }

 

[datalukas]

return true war vorhanden, ist nur rausgerutscht, als ich das Auskommentierte entfernt habe. Beim zweiten hast du Recht.

 

[Fonce]

Also für einen sauberen Stil gehört der Pointer "int* primzahlen" auf der Funktion raus, oder sollte als Argument(const int* primzahlen) mit übergeben werden.
Auch "int anzahlPrimfelder" hat nichts in der Funktion zu suchen, den die Funktion heißt ist_primzahl und nicht ist_primzahl_und_zähle_primzahlen

 

[maxwell-cs]

was man noch verbessern kann: du hast in ist_primzahl zwei primzahltests eingebaut: einen für den input und einen für die interne liste von primzahlen. es gibt dafür keinen grund:

 bool ist_primzahl(long long zahl)
 {
    int potPrimzahl;
    int i = 0;
    while(primzahlen[i] < sqrt((double)zahl + 1))
    {
       if(zahl % primzahlen[i] == 0) {
          return false;
       }
       if(i < anzahlPrimfelder - 1) {
          ++i;
       }
       else {
          for (potPrimzahl = primzahlen[i]+2; !ist_primzahl(potPrimzahl); potPrimzahl += 2);
          primzahlen[i + 1]= potPrimzahl;
          ++anzahlPrimfelder;
          ++i;
       }
    }
    return true;
 }

 

[datalukas]

@maxwell-cs Du meinst also rekursive Programmierung. Das geht natürlich auch. Bringt das performancetechnisch denn einen Vorteil?
@Fonce Woher weiß ich dann, wieviele Felder schon mit Primzahlen belegt sind?

 

[maxwell-cs]

das hauptkriterium wäre hier weniger performance als vielmehr sauberer code und die vermeidung von redundanz.

ob diese lösung etwas schneller oder etwas langsamer ist, ist (mir) erstmal ohne profiling unklar. da die maximimale rekursionstiefe aber sowieso nur 1 ist, wird es auf jeden fall nur einen geringen unterschied machen und sollte daher zugunsten des sauberen codes so gemacht werden.

wenn man vermeiden will, dass dann bei der tatsächlichen ausführung eine rekursion stattfindet, kann man die funktion inline machen, mit optimierungen kompilieren und hoffen, dass der compiler sie ein mal inline ersetzt. das sind dann aber mikrooptimierungen, die dich wohl erstmal nicht zu interessieren brauchen.

 

[Fonce]

Um so mehr ich mir den Code grade angeschaut habe umso mehr merke ich das schon die Bezeichnung der Funktion nicht mit dem übereinzustimmen scheint was du eigentlich damit machen willst.

Es scheint ja als wolltest du dir alle Primzahlen aus einem Zahlenbereich holen. Wenn ich damit richtig liege denk mal über eine funktion mit folgendem Header nach.

void getPrimsInRange(const long long firstNumber, const long long lastNumber, long long* listOfPrims, const long long sizeOfList);

 

[antred]

void getPrimsInRange(const long long firstNumber, const long long lastNumber, long long* listOfPrims, const long long sizeOfList);

Warum deklarierst du die Parameter als const? Die Werte von Argumenten im Funktionsrumpf nicht zu verändern ist zwar guter Stil, aber so weit zu gehen, ein für den Aufrufer völlig nutzloses const in die Funktionsdeklaration aufzunehmen ... ich weiß nicht.

 

[Fonce]

Guter Stil ist unveränderliche Werte als diese in der Deklaration zu kennzeichnen!
Der Parameter " long long* listOfPrims" soll ja z.B. veränderbar sein und um dies deutlich zu machen besitzt er schon in der Deklaration kein const!
Mir kam das const auch lange zeit unnötig vor, aber wenn man sich ein wenig mit dem Thema beschäftigt merkt man das es absolut sinnvoll ist. Wenn jemand später z.B. deinen Code bearbeiten möchte und dann auf die Idee kommt, Parameter die eigentlich nicht verwändert werden dürfen zu ändern wird er durch das const in der Deklaration schon zur Kompilierzeit darauf hingewiesen bzw. der Kompiler wird hier schon abbrechen.

 

[antred]

Guter Stil ist unveränderliche Werte als diese in der Definition zu kennzeichnen!
Der Parameter " long long* listOfPrims" soll ja z.B. veränderbar sein und um dies deutlich zu machen besitzt er schon in der Definition kein const!
Mir kam das const auch lange zeit unnötig vor, aber wenn man sich ein wenig mit dem Thema beschäftigt merkt man das es absolut sinnvoll ist. Wenn jemand später z.B. deinen Code bearbeiten möchte und dann auf die Idee kommt, Parameter die eigentlich nicht verwändert werden dürfen zu ändern wird er durch das const in der Definition schon zur Kompilierzeit darauf hingewiesen bzw. der Kompiler wird hier schon abbrechen.

Versteh mich nicht falsch, ich habe gar nichts gegen const. Wo es Sinn macht (Referenz/Pointer-Argumente), sollte man es IMMER einsetzen, aber für einen Übergabeparameter wie long long firstNumber sehe ich diesen Sinn nur begrenzt. Überleg dir mal, was dieses const eigentlich aussagt:

Die Funktion getPrimsInRange() sagt:
Lieber Aufrufer, ich verspreche dir, den Wert des Übergabeparameters firstNumber nicht zu verändern.

Das ist dem Aufrufer aber vollkommen Wurscht, da die Funktion sowieso nur eine Kopie des übergebenen Werts in die Finger bekommt. Den einzigen Nutzen, den das const hier hat, ist eben zu erzwingen, dass du in deinem Funktionsrumpf den Wert des Parameters nicht verändern kannst ... was man ja auch, wie ich schon gesagt habe, nicht tun sollte. Aber nur deswegen die Schnittstelle der Funktion mit einem für den Aufrufer absolut nutzlosen const künstlich aufzublähen, halte ich nicht für guten Stil.

 

[Fonce]

Wie schon gesagt, für mich ist es eben kein "künstlich aufzublähen"

 

[datalukas]

@Fonce Weißt du eigentlich, wozu die Funktion sein soll? Im Grunde ist der Name doch genau richtig, denn die Aufgabe der Funktion ist, herauszufinden, ob der Parameter eine Primzahl ist. Nach meinem System muss dafür halt ein Array nach und nach und je nach Bedarf mit Primzahlen gefüllt werden, aber alles zum Zweck, herauszufinden, ob zahl eine Primzahl ist. Die Funktion ist übrigens für das Programm in Post 87 gedacht.

Und noch was:
Wie gesagt, habe da nicht soviel Erfahrung. Warum ist es kein sauberer Stil, anzahlPrimzahlen zu benützen? Ich weiß ehrlich gesagt nicht, wie ich es als Paramterwert einbauen kann, ohne während dem Funktionsablauf zu ändern. Denn nur die Funktion selber "weiß", wieviele neue Primzahlen erzeugt werden oder ob überhaupt.

Übrigens ist es mir schleierhaft, warum die Funktion mit diesem Inhalt nicht funktioniert (Layout ist nicht gut, liegt aber am Code-Tag hier):

   if(zahl%2==0)
			return false;
		if(zahl%3==0)
			return false;
		if(zahl%5==0)
			return false;
		if(zahl%7==0)
			return false;
		if(zahl%11==0)
			return false;
		if(zahl%13==0)
			return false;
		if(zahl%17==0)
			return false;
		if(zahl%23==0)
			return false;
		for(int i = 23; i<=sqrt((double)zahl)+1;i+=2)
		{
			if(zahl%i==0)
				return false;
		}
		return true;

 

[Fonce]

Eine Funktion sollte aber in sich konsistent sein. Es gibt Fälle in denen eine globale Variable Sinn ergibt, aber dieser Anwendungsfall gehört nicht dazu.