Javakurs/Übungsaufgaben/Primzahlenaufgabe - Versionsgeschichte

Bmay: kategorisiert, rechtschreibung korrigert

2013-02-24T14:34:19Z

kategorisiert, rechtschreibung korrigert

← Nächstältere Version		Version vom 24. Februar 2013, 14:34 Uhr
Zeile 1:		Zeile 1:
	=Primzahlen=		=Primzahlen=

	Als [[wikipedia:Primzahl\|Primzahlen]] bezeichnet man alle natürlichen Zahlen, die nur durch sich selbst und ~~eins~~ teilbar sind. Also zum Beispiel 2, 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 Primzahlenfinder==		==Einfacher Primzahlenfinder==
Zeile 15:		Zeile 15:
	Für die 25 würde der Algorithmus (ob 25 prim ist) also folgendermaßen 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 Algorithmus durchgelaufen ist, ohne einen Teiler für <code>x</code> gefunden zu haben, so muss <code>x</code> 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 Modulo-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, die die 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==
Zeile 30:		Zeile 30:
	'''Vorbemerkung:'''		'''Vorbemerkung:'''

	Diese Aufgabe kann auf vielerlei Arten gelöst werden und ist weniger zum Verständnis von Schleifen, Arrays, Bedingungen und Co gedacht~~, sondern vielmehr, um~~ die sinnvolle Anwendung dieser Konzepte ~~zu üben~~.		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.		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 <code>x</code> 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 <code>x</code> nur auf Teilbarkeit durch alle ~~Primzahlen, die kleiner~~ <code>x/2</code> ~~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 Algorithmus aus Aufgabe a) so, dass zum Überprüfen von Zahl <code>x</code> nur alle ~~Primzahlen~~ kleiner <code>x/2</code> 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:'''
Zeile 46:		Zeile 46:
	Wie viele 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)~~, das 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:'''
Zeile 52:		Zeile 52:
	* 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 herauszufinden.		* 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:'''
Zeile 68:		Zeile 67:
	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 heißt 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.		Wie man sieht, spart man hier schon ein paar Überprüfungen.
Zeile 95:		Zeile 94:


	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)		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)

	==== Andy ====		==== Andy ====
Zeile 101:		Zeile 100:
	-->		-->

	[[Kategorie:Java]]		[[Kategorie: Java]]
	[[Kategorie:Java_Aufgaben]]		[[Kategorie: Java_Aufgaben]]
			[[Kategorie: Javakurs]]

Jörg F: hat „Javakurs2007/Primzahlenaufgabe“ nach „Javakurs/Übungsaufgaben/Primzahlenaufgabe“ verschoben: wikistruktur

2010-08-01T11:48:33Z

hat „Javakurs2007/Primzahlenaufgabe“ nach „Javakurs/Übungsaufgaben/Primzahlenaufgabe“ verschoben: wikistruktur

← Nächstältere Version	Version vom 1. August 2010, 11:48 Uhr
(kein Unterschied)

130.149.24.73: /* Kommentare */

2010-03-19T16:32:54Z

Kommentare

← Nächstältere Version		Version vom 19. März 2010, 16:32 Uhr
Zeile 86:		Zeile 86:
	== Kommentare ==		== 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 ;)		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 ;)

	~~Ich glaube es gibt 169 primzahlen glaube ich.. hat das noch jemand?~~

	<!--		<!--
Zeile 95:		Zeile 93:
	==== Robert ====		==== Robert ====
	Na mal schauen, ob irgendjemand diese Funktion wirklich benutzt. Ich fände es jedenfalls toll.		Na mal schauen, ob irgendjemand diese Funktion wirklich benutzt. Ich fände es jedenfalls toll.
	~~-->~~

	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)		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)

			==== Andy ====
			wurde meiner Meinung nach eingepflegt!
			-->

	[[Kategorie:Java]]		[[Kategorie:Java]]
	[[Kategorie:Java_Aufgaben]]		[[Kategorie:Java_Aufgaben]]

Andre: /* Einfacher Primzahlenfinder */

2009-03-24T15:15:45Z

Einfacher Primzahlenfinder

← Nächstältere Version		Version vom 24. März 2009, 15:15 Uhr
Zeile 13:		Zeile 13:
	* 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.		* 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 folgendermaßen ablaufen ~~(die Zahlen 1 bis 24 sollten vorher schon gecheckt werden)~~:		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>

Andre: /* Einfacher Primzahlenfinder */

2009-03-24T15:13:39Z

Einfacher Primzahlenfinder

← Nächstältere Version		Version vom 24. März 2009, 15:13 Uhr
Zeile 13:		Zeile 13:
	* 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.		* 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 folgendermaßen ablaufen:		Für die 25 würde der Algorithmus also folgendermaßen ablaufen (die Zahlen 1 bis 24 sollten vorher schon gecheckt werden):

	25 / 2 = 12 rest 1<br>		25 / 2 = 12 rest 1<br>
Zeile 25:		Zeile 25:

	* Ihr braucht zwei verschachtelte Schleifen. Eine, die die 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 durch jede kleinere Zahl teilt um auf Teilbarkeit zu überprüfen.


	==Optimierung des Algorithmus==		==Optimierung des Algorithmus==

Bmay: KAtegorisiert

2009-03-17T13:31:06Z

KAtegorisiert

← Nächstältere Version		Version vom 17. März 2009, 13:31 Uhr
Zeile 99:		Zeile 99:

	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)		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)

			[[Kategorie:Java]]
			[[Kategorie:Java_Aufgaben]]

Bmay: /* Kommentare */ Nametag vergessen

2009-03-04T14:23:45Z

Kommentare: Nametag vergessen

← Nächstältere Version		Version vom 4. März 2009, 14:23 Uhr
Zeile 98:		Zeile 98:
	-->		-->

	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.		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)

Bmay: /* Kommentare */ Weitere Optimierung des Primalgorithmus

2009-03-04T14:23:24Z

Kommentare: Weitere Optimierung des Primalgorithmus

← Nächstältere Version		Version vom 4. März 2009, 14:23 Uhr
Zeile 97:		Zeile 97:
	Na mal schauen, ob irgendjemand diese Funktion wirklich benutzt. Ich fände es jedenfalls toll.		Na mal schauen, ob irgendjemand diese Funktion wirklich benutzt. Ich fände es jedenfalls toll.
	-->		-->

			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.

130.149.17.38: /* Kommentare */

2008-04-08T09:55:32Z

Kommentare

← Nächstältere Version		Version vom 8. April 2008, 09:55 Uhr
Zeile 87:		Zeile 87:
	== Kommentare ==		== 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 ;)		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 ;)

			Ich glaube es gibt 169 primzahlen glaube ich.. hat das noch jemand?

	<!--		<!--

89.247.214.99: /* Optimierung des Algorithmus */

2008-04-07T18:41:58Z

Optimierung des Algorithmus

← Nächstältere Version		Version vom 7. April 2008, 18:41 Uhr
Zeile 39:		Zeile 39:

	Um zu ermitteln, ob eine Zahl <code>x</code> 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 <code>x</code> nur auf Teilbarkeit durch alle Primzahlen, die kleiner ~~oder gleich~~ <code>x/2</code> 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 Primzahlen, die kleiner <code>x/2</code> sind, ü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 <code>x</code> nur alle Primzahlen kleiner ~~oder gleich~~ <code>x/2</code> durchlaufen werden.		Optimiert nun den Algorithmus aus Aufgabe a) so, dass zum Überprüfen von Zahl <code>x</code> nur alle Primzahlen kleiner <code>x/2</code> durchlaufen werden.

	'''Optionale Aufgabe:'''		'''Optionale Aufgabe:'''