Verständnisproblem mit return

freakC++

Hallo zusammen,
ich stehe gerade aufm Schlauch. Ich habe hier einen Code, der prüft, ob eine Zahl eine Primzahl ist. Ich prüfe einfach, ob die Zahl nur zwei Teile hat, doch verstehe ich nicht ganz die Arbeitsweise dieser Funktion:

bool Prime(unsigned int k)
{
	if (n <= 2 ) return false;
	unsigned int i=2, limit =k/2;

	for (; i<=limit; ++i)
		if(k%i==0)
			return false;

	return true;
}

Wenn k durch i teilbar ist, dann wird false zurückgegen. Aber woher weiß ich dann, ob es eine Primzahl ist? Ich muss also prüfen, ob zweimal false zurückgeben wird? Außerdem wird in jedem Fall ja true zurückgegeben, da das Programm ja dahin kommt (oder hört es beim ersten true auf...sowas wie break)?

Irgendwie kapier ich das gerade nicht und bitte daher um eure Hilfe
Vielen Dank
lg, freakC++

drakon

return verlässt sofort die Funktion. Sprich es wird kein Code mehr aufgerufen. (mal abgesehen von Destruktoren).

Die Funktion übernimmt einfach eine Zahl und gibt true zurück, wenn sie eine Primzahl ist. Warum willst du da zwei Zahlen überprüfen?!

unskilled

2 ist keine Primzahl?

bool Prime(unsigned int k)
{
  if (k < 2)
    return false;
  if (k%2 == 0)
    return k==2 ? true : false;

  unsigned int limit = unsigned int(sqrt(float(k)));

  for (unsigned int i=3; i <= limit; i += 2)
    if(k%i == 0)
      return false;

  return true;
}

bei limit bin ich mir nicht ganz sicher, aber sollte hinkommen...

bb

PS: Falls die Fkt sehr zeitkritisch sein sollte, dann nimmst du besser nen Array mit Primzahlen und prüfst, ob eine der Primzahlen diese Zahl teilt...

Also, ein return springt aus der Funktion, da wird nix mehr danach ausgeführt!
Sobald eine Zahl nur durch sich und 1 Teilbar ist, also keine andere, dann ist es eine.
Wenn also in der Schleife die Teilung funktioniert (k/i gibt keinen Rest, das macht Modulo) ist es keine Primzahl.

Aber einen Fehler hat die Funktion:
Die Teilung durch 2 als Limit!
13/2 = 6
13 ist eine Primzal, 6 aber nicht, trotzdem returnd die Funktion true
Liegt an der Rundung.
Lass die Teilung einfach weg.

wenn k durch i teilbar ist und 1 < i < k gilt, kann k keine Primzahl sein. Deswegen wird kan auch false zurückgegeben. Der Anfang ist aber falsch. 2 ist natürlich prim. Deine Funktion liefert aber false zurück.

theta

2 ist keine Primzahl?

*g* doch, per Definition.
Simon

unskilled

theta schrieb:

2 ist keine Primzahl?

*g* doch, per Definition.
Simon

ach echt?
deshalb hab ich ja auch ne fkt hingeschrieben, die richtig funktioniert...

volkard

theta schrieb:

2 ist keine Primzahl?

*g* doch, per Definition.
Simon

Beweis:
http://www.getdigital.de/products/Two_is_the_oddest_prime/lng/1/her/rss

Ohne Fließkommazahl und ohne Wurzel könnte man es noch so machen

bool prim(unsigned x)
{
	if (x<=4)       return x & 2; //< fuer 0,1,2,3,4
	if ((x & 1)==0) return false; //< gerade Zahlen
	unsigned t = 1;     //< Zu testender Teiler
	unsigned q = 1;     //< Quadrat des Teilers
	// Invariante: t*t == q
	for (;;) {
		unsigned oldq = q;
		t += 2;          //< Teiler in 2er-Schritten testen
		q += (t-1) << 2; //< Invariante herstellen
		// Alle Teiler von x muessen kleiner oder gleich
		// der Wurzel von x sein. Wenn wir ein t mit x<t^2
		// erreicht haben, kann abgebrochen werden.
		// Ausserdem fangen wir noch einen Ueberlauf ab...
		if (x<q || q<oldq) return true;
		if ((x % t)==0) return false; // Teiler gefunden -> x nicht prim
	}
}

volkard

Neulich hat eine Messung ergeben, daß s+=i*i;++i; genauso viele takte braucht wie s+=q;q+=2*i+1;++i;
ich nehme an, daß dein code langsamer ist, weil die register pressure größer ist als for(t=3;t*t<x;++t).
außerdem, welcher überlauf? ist der nur theoretisch oder kann der wirklich passieren?

SeppJ

primzahlzaehler schrieb:

Ohne Fließkommazahl und ohne Wurzel könnte man es noch so machen

Wenn's darum geht, das Verfahren zu verbessern, kann man auch gleich Miller-Rabin oder AKS-Test verwenden. Dann hätte der Threadersteller aber vermutlich noch mehr Fragen, wie das funktioniert.

Sebastian Pizer

volkard schrieb:

außerdem, welcher überlauf? ist der nur theoretisch oder kann der wirklich passieren?

So, wie es aussieht, soll "q<oldq" wohl den Fall abfangen, dass q überläuft und dann kleiner ist als der alte Wert. Ich schätze, ohne diese Bedingung könnte es bei großen Eingaben (Primzahl in der Nähe von unsigned(-1) ) zu einer Endlosschleife führen.

Ich weiß nicht, wie es mit der Geschwindigkeit aussieht. Aber was die Genauigkeit bei Fließkommazahlen angeht, muss man ja etwas aufpassen. Wichtig ist, dass limit eine möglichst kleine Zahl ist, die x <= limit*limit erfüllt. Kommt dann natürlich drauf an, wieviele signifikante Stellen ein float bzw double hat und wieviele Bits ein unsigned hat, etc. Der paranoide Programmierer könnte dann so etwas schreiben:

unsigned limit = std::sqrt(float(limit));
while (limit*limit<x) ++limit;

Aber auch hier gibt es eine Überlaufgefahr bei limit*limit und Zahlen x, die sehr nah an unsigned(-1) dran sind.

edit: Miller-Rabin versteht doch keiner

Gruß,
SP