primzahlen

Hi,

anbei code um primzahlen auszugeben...
warum brauch ich hier folgende bedingung? j*j <= i

#include <iostream>

void output_prime(int m) {
  for (int i = 2; i <= m; i++) {
        bool is_prime = true;

        for (int j = 2; j*j <= i; j++) {

            if (i % j == 0) {
                is_prime = false;
                break;    
            }
        }   

        if (is_prime) {
          cout << i << " ";
        }
    }
}

int main() {  
  output_prime(200);
  return 0;
}

Man braucht es nicht. Du könntest auch alle Zahlen von 2 bis i-1 testen. Das ist eine Optimierung. Es reicht eigentlich von 2 bis sqrt(i) zu testen. Wenn man bis dahin keinen Teiler gefunden hat, dann ist die Zahl eine Primzahl (warum das so ist kannst du dir einfach überlegen). Die Bedingung j <= sqrt(i) wurde einfach umgeformt zu j*j <= i womit wir bei deinem Code sind.

sebi707 schrieb:

Die Bedingung j <= sqrt(i) wurde einfach umgeformt zu j*j <= i

vielleicht weil jemand dachte Multiplizieren geht schneller als Wurzelziehen (ob das stimmt weiß ich nicht).

Für eine einzelne Zahl mit Sicherheit. Allerdings muss man bedenken, dass man bei dieser Methode in jedem Durchlauf etwas multiplizieren muss, die Wurzel müsste man aber nur einmal ziehen. Allerdings gibt es im Standard keine sqrt Funktion für Integer und mischen mit float/double finde ich immer ungut. Wer wirklich einen schnellen Primzahltest braucht nutzt sowieso andere Algorithmen.

Columbo

Allerdings gibt es im Standard keine sqrt Funktion für Integer und mischen mit float/double finde ich immer ungut.

In diesem Fall in Ordnung, da wir mit int s arbeiten. double 's Mantisse packt das.

ob das stimmt weiß ich nicht

Wurzelziehen ist asymptotisch viel, viel besser. Daher ist es auch i.d.R. effizienter, die Wurzel zu ziehen und Teiler unter ihr zu suchen.

Wir können gar eine obere Schranke der Wurzel selbst berechnen, die nah genug ist und nicht zu viele, überflüssige Prüf-Divisionen impliziert. Aber ob das wirklich signifikant schneller ist als sqrt …

Unser Prof sieht das auch tatsächlich als Fehler, wenn man sqrt auf int's anwendet.
Das Gleiche bei pow (wir programmieren C).

War aber auch zumindest auf meinem System und unter VS um ein Faktor 2 schneller, zu Quadrieren anstatt Wurzel zu ziehen.

Das einzige Problem vom Quadrieren ist ja, dass man schneller bei hohen Zahlen den Zahlenbereich der verwendeten Datenstruktur verlässt, als wenn man die Wurzel verwenden würde.

Aber das sollte bei solchen Beispielen wohl eher weniger relevant sein, zur not kann man sich ja immer noch dicken Zahlen besorgen, falls man das denn will.

Columbo

War aber auch zumindest auf meinem System und unter VS um ein Faktor 2 schneller, zu Quadrieren anstatt Wurzel zu ziehen.

Etwa zehntausend Multiplikationen sollen doppelt so schnell sein wie ein einziges sqrt ?!
Oder was für N hast du probiert? Und wie genau hast du gemessen?

Das Gleiche bei pow (wir programmieren C).

Hmm. Also entsprechende Funktionen selber zu proggern und zu verifizieren wäre sinnvoll und gut, aber sqrt packt int s, alle mindestens auf x86. Dafür leg' ich meine Hand ins Feuer.

Skym0sh0

Arcoth schrieb:

War aber auch zumindest auf meinem System und unter VS um ein Faktor 2 schneller, zu Quadrieren anstatt Wurzel zu ziehen.

Etwa zehntausend Multiplikationen sollen doppelt so schnell sein wie ein einziges sqrt ?!
Oder was für N hast du probiert? Und wie genau hast du gemessen?

Könnte mir vorstellen, dass ers ohne Optimierungen hat, sod ass in jedem Schleifendurchlauf auch die Wurzel nochmal berechnet wird.