Java Warum nur bis zur Wurzel testen?

[Hendoul]

Hi

Ich musste an einem Vorstellungsgespräch die ersten 100 Primzahlen ausgeben (Java). Jetzt habe ich mal noch kurz recherchiert was es denn so alles für effiziente Wege gibt. Dabei bin ich auf diese Website gestossen:

https://www.mkyong.com/java/how-to-determine-a-prime-number-in-java/

Dort steht:

With some more efficient coding, we notice that you really only have to go up to the square root of n, because if you list out all of the factors of a number, the square root will always be in the middle (if it happens to not be an integer, we're still ok, we just might over-approximate, but our code will still work).

Kann mir jemand erklären warum man nur bis zur Wurzel testen muss?

 

[HominiLupus]

Weil x * y das Gleiche ist wie y * x.
Also bei der Zahl 12 z.B. ist 3 * 4 gleich wie 4 * 3 also muss man nur bis zur Wurzel iterieren d.h. nur bis 3. Wenn man bis dahin keinen Teiler gefunden hat, wird man keinen mehr finden.

 

[Jojo_44]

Der Algorithmus heißt "Sieb des Eratosthenes". Hier gibt es ein gutes Video drüber - zum Ende hin wird auch die Frage beantwortet, warum man nur bis zur Wurzel iterieren muss.

https://www.youtube.com/watch?v=Cg8P4GNPe0I

mfg Jojo

 

[andy_m4]

die Frage beantwortet, warum man nur bis zur Wurzel iterieren muss.

. was sich aber jedem eigentlich erschließen sollte, der in Mathe nicht eine vollkommene Niete war.

Und ich geh mal davon aus, dass jemand der programmiert über ein minimales mathematisches Grundverständnis verfügt. Vielleicht ist diese Annahme aber auch zuuu optimistisch. :-)

 

[crvn075]

Der Algorithmus heißt "Sieb des Eratosthenes".

Das mit der Wurzel hat mit dem Sieb des Eratosthenes an sich nichts zu tun. Klar macht es Sinn, sich die Eigenschaft auch beim Sieb zu nutze zu machen, aber du kannst die auch genau so gut als Optimierung nutzen, um den naiven "stupide-alle-Teiler bis-n-durchprobieren" Algorithmus aufzupeppen.

 

[Hendoul]

Danke jedenfalls für die Antworten, das Video hat geholfen mir auf die Sprünge zu helfen ^^

Naja, ich arbeite jetzt 10 Jahre auf dem Beruf und musste noch nie wirklich was mathematisches einsetzen was in etwa über Grundoperationen hinausgeht. Hängt halt davon ab in welchem Bereich man arbeitet.

 

[maxator]

Sehr effektiv ist übrigens auch (mit kleinem Augenzwinkern):
System.out.print("2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97");

Wie hast du es denn gelöst. Zumindest nur jede 2. Zahl überprüft?

 

[Lacritz]

Sehr effektiv ist übrigens auch (mit kleinem Augenzwinkern):
System.out.print("2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97");

Wie hast du es denn gelöst. Zumindest nur jede 2. Zahl überprüft?

Schau dir nochmal die genaue Aufgabenstellung des TE an.

 

[maxator]

Schau dir nochmal die genaue Aufgabenstellung des TE an.

Dann wird der Befehl halt etwas länger. Es sollte nur verdeutlichen, dass der effektifste Weg manchmal näher liegt als man glaubt. Wenn man diesen Lösungsansatz präsentiert, (am besten mit vorher durch effektiven Algorithmus herausgefundenen Zahlen) sticht man zumindest hervor

Bleibt meine Frage an den Themenersteller.