Sitzung: Jeden Freitag in der Vorlesungszeit ab 16 Uhr c. t. im MAR 0.005. In der vorlesungsfreien Zeit unregelmäßig (Jemensch da?). Macht mit!

Javakurs/Übungsaufgaben/Primzahlenaufgabe: Unterschied zwischen den Versionen

K (format)
K (kategorisiert, rechtschreibung korrigert)
 
(16 dazwischenliegende Versionen von 10 Benutzern werden nicht angezeigt)
Zeile 1: Zeile 1:
 
=Primzahlen=
 
=Primzahlen=
  
Als [http://de.wikipedia.org/wiki/Primzahl Primzahlen] bezeichnet man alle natürlichen Zahlen die nur durch sich selbst und eins teilbar sind. Also zum beispiel 3, 5, 7, 11, 13, usw. Die 1 ist per definition keine Primzahl.
+
Als [[wikipedia:Primzahl|Primzahlen]] bezeichnet man alle natürlichen Zahlen, die nur durch sich selbst und die Zahl Eins teilbar sind. Also zum Beispiel 2, 3, 5, 7, 11, 13, usw. Die 1 ist per Definition keine Primzahl.
  
==Einfacher Primzahlen finder==  
+
==Einfacher Primzahlenfinder==  
'''Mindestkenntnisse:''' Schleifen, Basistypen, Bedingungen
 
  
 
'''Aufgabe:'''  
 
'''Aufgabe:'''  
  
Schreibt ein Programm das die ersten n Primzahlen bestimmt und ausgibt.
+
Schreibt ein Programm, das die ersten <code>n</code> Primzahlen bestimmt und ausgibt.
  
 
'''Hinweise:'''
 
'''Hinweise:'''
  
* Der simpelste Algorithmus um zu ermitteln ob eine Zahl x eine Primzahl ist, ist einfach x durch jede Zahl kleiner als x zu teilen und zu überprüfen ob ein Rest übrig bleibt.
+
* Der einfachste Algorithmus um zu ermitteln, ob eine Zahl <code>x</code> eine Primzahl ist, besteht darin, <code>x</code> durch jede Zahl kleiner als <code>x</code> zu teilen und zu überprüfen, ob ein Rest übrig bleibt.
  
Für die 25 würde der Algorithmus also folgendermassen ablaufen:
+
Für die 25 würde der Algorithmus (ob 25 prim ist) also folgendermaßen ablaufen:
  
25 / 2 = 12 rest 1<br>
+
25 / 2 = 12 Rest 1<br>
25 / 3 = 8 rest 1<br>
+
25 / 3 = 8 Rest 1<br>
25 / 4 = 6 rest 1<br>
+
25 / 4 = 6 Rest 1<br>
25 / 5 = 5 rest 0 -> 25 ist keine Primzahl
+
25 / 5 = 5 Rest 0 -> 25 ist keine Primzahl
  
Wenn der Algorithmuss durchgelaufen ist ohne einen Teiler für x gefunden zu haben muss x eine Primzahl sein.
+
Wenn der Algorithmus durchgelaufen ist, ohne einen Teiler für <code>x</code> gefunden zu haben, so muss <code>x</code> eine Primzahl sein.
  
* Der operator % gibt den Rest zurück der beim teilen von zwei Zahlen übrig bleibt.
+
* Der Modulo-Operator <code>%</code> gibt den Rest zurück, der beim Teilen von zwei Zahlen übrig bleibt.
 
 
* Ihr braucht zwei verschachtelte Schleifen, eine welche die zu überprüfende Zahlen 1 bis n hochzählt und eine die jede dieser Zahlen durch jede kleinere Zahl teilt um auf teilbarkeit zu überprüfen.
 
  
 +
* Ihr braucht zwei verschachtelte Schleifen. Eine, die die Zahlen 1 bis n hochzählt und eine, die jede dieser Zahlen mit jeder kleineren Zahl auf Teilbarkeit überprüft.
  
 
==Optimierung des Algorithmus==
 
==Optimierung des Algorithmus==
  
'''Mindestkenntnisse:''' Schleifen, Basistypen, Bedingungen, Arrays<br>
+
'''Vorbemerkung:'''
'''empfohlenen Kenntnisse:''' Schleifen, Basistypen, Bedingungen, Arrays, Methoden
 
  
'''Vorbemerkung:'''
+
Diese Aufgabe kann auf vielerlei Arten gelöst werden und ist weniger zum Verständnis von Schleifen, Arrays, Bedingungen und Co gedacht. Vielmehr soll die sinnvolle Anwendung dieser Konzepte vertieft werden.
  
Diese Aufgabe kann auf vielerlei Arten gelösst werden und ist weniger zum verstehen von Schleifen, Arrays, Bedingungen und Co gedacht
+
Die Hinweise sind nur als Anregungen zum Lösen der Aufgabe gedacht, falls man selbst gar keine Idee hat.  
sondern vielmehr um die sinnvolle Anwendung dieser Konzepte zu üben.
 
Die Hinweise sind nur als Anregungen zum lösen der Aufgabe gedacht falls man selbst gar keine Idee hat.  
 
 
Da es viele Möglichkeiten gibt die Aufgabe zu lösen, die Hinweise jedoch nur einen Weg aufzeigen, solltet ihr erstmal probieren selbst eine Lösung zu finden.
 
Da es viele Möglichkeiten gibt die Aufgabe zu lösen, die Hinweise jedoch nur einen Weg aufzeigen, solltet ihr erstmal probieren selbst eine Lösung zu finden.
  
 
'''Aufgabe:'''
 
'''Aufgabe:'''
  
Um zu ermitteln ob eine Zahl x eine Primzahl ist muss man diese nicht durch sämtliche kleineren Zahlen teilen.  
+
Um zu ermitteln, ob eine Zahl <code>x</code> eine Primzahl ist, muss man diese nicht durch sämtliche kleineren Zahlen teilen.  
Tatsächlich reicht es wenn man x nur auf Teilbarkeit durch alle Primzahlen die kleiner als x/2 sind überprüft (warum dies so ist wird weiter unten beim Punkt "Hintergrund" erklärt).
+
Tatsächlich reicht es, wenn man <code>x</code> nur auf Teilbarkeit durch alle Zahlen <code>Z<x/2</code> überprüft (warum dies so ist, wird weiter unten beim Punkt "Hintergrund" erklärt).
  
Optimiert nun den Algorithmuss aus Aufgabe a) so dass zum überprüfen von Zahl x nur alle Primzahlen kleiner x/2 durchlaufen werden.  
+
Optimiert nun den Algorithmus aus Aufgabe a) so, dass zum Überprüfen von Zahl <code>x</code> nur alle Zahlen kleiner <code>x/2</code> durchlaufen werden.  
  
 
'''Optionale Aufgabe:'''
 
'''Optionale Aufgabe:'''
  
Wieviele Primzahlen gibt es zwischen 1 und 10? Wieviele zwischen 1 und 100? 1 und 1000? ...
+
Wie viele Primzahlen gibt es zwischen 1 und 10? Wieviele zwischen 1 und 100? 1 und 1000? ...
  
Schreibt euch ein Programm (oder eine Methode) die euch das Verhältniss von gefundenen Primzahlen zu der Anzahl der überprüften Zahlen ausgibt.
+
Schreibt euch ein Programm, das euch das Verhältniss von gefundenen Primzahlen zu der Anzahl der überprüften Zahlen ausgibt.
 
        
 
        
 
'''Hinweise:'''   
 
'''Hinweise:'''   
  
* Speichert euch beim durchlaufen der Zahlen jede gefundene Primzahl in einem Array.
+
* Speichert euch beim Durchlaufen der Zahlen jede gefundene Primzahl in einem Array.
 
 
* Wie groß muss das Array zum speichern der gefundenen Primzahlen in Abhängigkeit von der Anzahl der zu überprüfenden Zahlen maximal sein? Die optionale Aufgabe hilft dies herrauszufinden.
 
  
 +
* Wie groß muss das Array zum Speichern der gefundenen Primzahlen, in Abhängigkeit von der Anzahl der zu überprüfenden Zahlen, maximal sein? Die optionale Aufgabe hilft, dies herauszufinden.
  
 
'''Hintergrund:'''
 
'''Hintergrund:'''
  
Der Algorithmus aus Aufgabe a ist zwar einfach aber nicht gerade sehr intelligent. Beispielsweise würde es auch reichen beim überprüfen einer Primzahl x nur die ersten x/2 Zahlen zu durchlaufen da beim teilen durch alle grösseren Zahlen nur noch ein Wert zwischen 1 und 2 rauskommen kann.
+
Der Algorithmus aus Aufgabe a ist zwar einfach, aber nicht gerade sehr intelligent. Beispielsweise würde es auch reichen, beim Überprüfen einer Primzahl <code>x</code> nur die ersten <code>x/2</code> Zahlen zu durchlaufen, da beim Teilen durch alle größeren Zahlen nur noch ein Wert zwischen 1 und 2 rauskommen kann.
  
 
Veranschaulichung:
 
Veranschaulichung:
  
23 / 11 = 2 rest 1<br>
+
23 / 11 = 2 rest 1<br>
23 / 12 = 1 rest 11<br>
+
23 / 12 = 1 rest 11<br>
23 / 13 = 1 rest 10<br>
+
23 / 13 = 1 rest 10<br>
23 / 14 = 1 rest 9<br>
+
23 / 14 = 1 rest 9<br>
...<br>
+
...<br>
23 / 22 = 1 rest 1<br>
+
23 / 22 = 1 rest 1<br>
  
Eine weitere Optimierungsmöglichkeit stellt die Tatsache dar dass eine Zahl die nicht durch zwei teilbar ist, auch nicht durch ein vielfaches von zwei teilbar sein wird. Praktisch heisst das, dass wir die zu überprüfende Zahl nur auf teilbarkeit durch die ungeraden Zahlen sowie der zwei überprüfen müssen.
+
Eine weitere Optimierungsmöglichkeit stellt die Tatsache dar, dass eine Zahl die nicht durch Zwei teilbar ist, auch nicht durch ein Vielfaches von Zwei teilbar sein wird. Praktisch heißt das, dass wir die zu überprüfende Zahl nur auf Teilbarkeit durch die ungeraden Zahlen sowie der Zwei überprüfen müssen.
  
 
Beispiel:
 
Beispiel:
  
25 / 2 = 12 rest 1 -> nicht durch zwei teilbar also auch nicht durch 4, 6, 8, 10, usw. -> nur ungerade Zahlen überprüfen<br>
+
* 25 / 2 = 12 rest 1 -> nicht durch zwei teilbar, also auch nicht durch 4, 6, 8, 10, usw. -> nur ungerade Zahlen überprüfen
25 / 3 = 8 rest 1<br>
+
* 25 / 3 = 8 rest 1
25 / 5 = 5 rest 0 -> keine Primzahl<br>
+
* 25 / 5 = 5 rest 0 -> keine Primzahl
 +
 
 +
Wie man sieht, spart man hier schon ein paar Überprüfungen.
 +
 
 +
Die Regel, dass alle Zahlen, die nicht durch 2 teilbar, sind auch nicht durch ein Vielfaches von 2 teilbar sind, lässt sich noch verallgemeinern. Das heißt:
 +
 
 +
Eine Zahl die nicht durch <code>t</code> teilbar ist, ist auch nicht durch ein Vielfaches von <code>t</code> teilbar.
 +
 
 +
Dies bedeutet im Endeffekt, dass wir beim Überprüfen von <code>x</code> nur alle Primzahlen kleiner <code>x/2</code> überprüfen müssen. Da alle anderen Zahlen Vielfache einer kleineren Zahl sind, welche wir schon überprüft haben.
 +
 
 +
== Kommentare ==
 +
Wenn du Anmerkungen zur Aufgabe hast oder Lob und Kritik loswerden möchtest, ist hier die richtige Stelle dafür. Klicke einfach ganz rechts auf "bearbeiten" und schreibe deinen Kommentar direkt ins Wiki. Keine Scheu, es geht nichts kaputt ;)
 +
 
 +
<!--
 +
Als kleine Starthilfe folgt ein Beispiel, wie so ein Kommentar formatiert sein könnte. Mit "Vorschau zeigen" kannst du dir ansehen, was deine Änderung bewirken würde, ohne wirklich etwas zu ändern.
 +
Du musst übrigens außerhalb dieses auskommentieren Bereichs schreiben ;)
 +
 
 +
==== Robert ====
 +
Na mal schauen, ob irgendjemand diese Funktion wirklich benutzt. Ich fände es jedenfalls toll.
  
Wie man sieht spart man hier schon ein paar Überprüfungen.
 
  
Die Regel dass alle Zahlen die nicht durch 2 teilbar sind auch nicht durch ein vielfaches von 2 teilbar sind lässt sich noch verallgemeinern. Das heisst:
+
Eigentlich reicht es sogar aus, alle Zahlen die kleiner oder gleich als die abgerundete Wurzel des Kandidaten sind zu untersuchen. Jede Zahl die größer als die Wurzel und ganzzahliger Teiler des Kandidaten ist, hat als der Ergebnis der Division eine Zahl die kleiner als die Wurzel ist.--[[Benutzer:Bmay|Bmay]] 14:23, 4. Mär. 2009 (UTC)
  
Eine Zahl die nicht durch x teilbar ist, ist auch nicht durch ein vielfaches von x teilbar.
+
==== Andy ====
 +
wurde meiner Meinung nach eingepflegt!
 +
-->
  
Dies bedeutet im Endeffekt dass wir beim überprüfen von x nur alle Primzahlen kleiner x / 2 überprüfen müssen. Da alle anderen Zahlen Vielfache einer kleineren Zahl sind welche wir schon überprüft haben.
+
[[Kategorie: Java]]
 +
[[Kategorie: Java_Aufgaben]]
 +
[[Kategorie: Javakurs]]

Aktuelle Version vom 24. Februar 2013, 14:34 Uhr

Primzahlen

Als Primzahlen bezeichnet man alle natürlichen Zahlen, die nur durch sich selbst und die Zahl Eins teilbar sind. Also zum Beispiel 2, 3, 5, 7, 11, 13, usw. Die 1 ist per Definition keine Primzahl.

Einfacher Primzahlenfinder

Aufgabe:

Schreibt ein Programm, das die ersten n Primzahlen bestimmt und ausgibt.

Hinweise:

  • Der einfachste Algorithmus um zu ermitteln, ob eine Zahl x eine Primzahl ist, besteht darin, x durch jede Zahl kleiner als x zu teilen und zu überprüfen, ob ein Rest übrig bleibt.

Für die 25 würde der Algorithmus (ob 25 prim ist) also folgendermaßen ablaufen:

25 / 2 = 12 Rest 1
25 / 3 = 8 Rest 1
25 / 4 = 6 Rest 1
25 / 5 = 5 Rest 0 -> 25 ist keine Primzahl

Wenn der Algorithmus durchgelaufen ist, ohne einen Teiler für x gefunden zu haben, so muss x eine Primzahl sein.

  • Der Modulo-Operator % gibt den Rest zurück, der beim Teilen von zwei Zahlen übrig bleibt.
  • Ihr braucht zwei verschachtelte Schleifen. Eine, die die Zahlen 1 bis n hochzählt und eine, die jede dieser Zahlen mit jeder kleineren Zahl auf Teilbarkeit überprüft.

Optimierung des Algorithmus

Vorbemerkung:

Diese Aufgabe kann auf vielerlei Arten gelöst werden und ist weniger zum Verständnis von Schleifen, Arrays, Bedingungen und Co gedacht. Vielmehr soll die sinnvolle Anwendung dieser Konzepte vertieft werden.

Die Hinweise sind nur als Anregungen zum Lösen der Aufgabe gedacht, falls man selbst gar keine Idee hat. Da es viele Möglichkeiten gibt die Aufgabe zu lösen, die Hinweise jedoch nur einen Weg aufzeigen, solltet ihr erstmal probieren selbst eine Lösung zu finden.

Aufgabe:

Um zu ermitteln, ob eine Zahl x eine Primzahl ist, muss man diese nicht durch sämtliche kleineren Zahlen teilen. Tatsächlich reicht es, wenn man x nur auf Teilbarkeit durch alle Zahlen Z<x/2 überprüft (warum dies so ist, wird weiter unten beim Punkt "Hintergrund" erklärt).

Optimiert nun den Algorithmus aus Aufgabe a) so, dass zum Überprüfen von Zahl x nur alle Zahlen kleiner x/2 durchlaufen werden.

Optionale Aufgabe:

Wie viele Primzahlen gibt es zwischen 1 und 10? Wieviele zwischen 1 und 100? 1 und 1000? ...

Schreibt euch ein Programm, das euch das Verhältniss von gefundenen Primzahlen zu der Anzahl der überprüften Zahlen ausgibt.

Hinweise:

  • Speichert euch beim Durchlaufen der Zahlen jede gefundene Primzahl in einem Array.
  • Wie groß muss das Array zum Speichern der gefundenen Primzahlen, in Abhängigkeit von der Anzahl der zu überprüfenden Zahlen, maximal sein? Die optionale Aufgabe hilft, dies herauszufinden.

Hintergrund:

Der Algorithmus aus Aufgabe a ist zwar einfach, aber nicht gerade sehr intelligent. Beispielsweise würde es auch reichen, beim Überprüfen einer Primzahl x nur die ersten x/2 Zahlen zu durchlaufen, da beim Teilen durch alle größeren Zahlen nur noch ein Wert zwischen 1 und 2 rauskommen kann.

Veranschaulichung:

23 / 11 = 2 rest 1
23 / 12 = 1 rest 11
23 / 13 = 1 rest 10
23 / 14 = 1 rest 9
...
23 / 22 = 1 rest 1

Eine weitere Optimierungsmöglichkeit stellt die Tatsache dar, dass eine Zahl die nicht durch Zwei teilbar ist, auch nicht durch ein Vielfaches von Zwei teilbar sein wird. Praktisch heißt das, dass wir die zu überprüfende Zahl nur auf Teilbarkeit durch die ungeraden Zahlen sowie der Zwei überprüfen müssen.

Beispiel:

  • 25 / 2 = 12 rest 1 -> nicht durch zwei teilbar, also auch nicht durch 4, 6, 8, 10, usw. -> nur ungerade Zahlen überprüfen
  • 25 / 3 = 8 rest 1
  • 25 / 5 = 5 rest 0 -> keine Primzahl

Wie man sieht, spart man hier schon ein paar Überprüfungen.

Die Regel, dass alle Zahlen, die nicht durch 2 teilbar, sind auch nicht durch ein Vielfaches von 2 teilbar sind, lässt sich noch verallgemeinern. Das heißt:

Eine Zahl die nicht durch t teilbar ist, ist auch nicht durch ein Vielfaches von t teilbar.

Dies bedeutet im Endeffekt, dass wir beim Überprüfen von x nur alle Primzahlen kleiner x/2 überprüfen müssen. Da alle anderen Zahlen Vielfache einer kleineren Zahl sind, welche wir schon überprüft haben.

Kommentare

Wenn du Anmerkungen zur Aufgabe hast oder Lob und Kritik loswerden möchtest, ist hier die richtige Stelle dafür. Klicke einfach ganz rechts auf "bearbeiten" und schreibe deinen Kommentar direkt ins Wiki. Keine Scheu, es geht nichts kaputt ;)