Bmay: In Kategorie eingeordnet

2009-03-09T08:53:09Z

In Kategorie eingeordnet

Ghandi: init

2007-04-11T10:12:02Z

init

Neue Seite

Für die Teilnehmer gilt: Die Aufgabe bitte zuerst vollständig lösen und mit einem Tutor vergleichen und erst dann diesen Lösungsvorschlag betrachten.

Einfacher Primzahlenfinder
<pre>
class PrimeNumbersA{

public static void main(String[] args){
int n = 1000; //Wir suchen alle Primzahlen zwischen 1 und n

//die Zahlen 2 bis n durchlaufen und sie auf Primzahlen überprüfen (1 lassen wir weg da Sie per definition keine Primzahl ist)
for(int toCheck = 2; toCheck <= n; toCheck++){

boolean dividerFound = false; //Hier speichern wir uns ob wir für die aktuelle Zahl (toCheck) einen Teiler gefunden haben

for(int z = 2; z < toCheck; z++){ //alle Zahlen kleiner als toCheck überprüfen

if( toCheck % z == 0 ){ //Falls der Rest 0 ist haben wir einen Teiler von toCheck gefunden...
dividerFound = true; //...damit haben wir einen Teiler gefunden und...
break; //...wir können die Schleife verlassen.
}
}

if(!dividerFound) //Falls wir keinen Teiler gefunden haben ist toCheck eine Primzahl
System.out.println(toCheck); //Primzahl ausgeben
}
}
}
</pre>

Optimierter Primzahlenfinder
<pre>
class PrimeNumbersB{

public static void main(String[] args){
int n = 100000; //Wir suchen alle Primzahlen zwischen 1 und n

//Wie viele Primzahlen werden wir zwischen 1 und n maximal finden? Wie gross muss unser Array maximal sein?
//Werte durch die optionale Aufgabe ermittelt
int maxPrimes;
if(n <= 13)
maxPrimes = n;
else if(n <= 47)
maxPrimes = n / 2;
else if(n <= 139)
maxPrimes = n / 3;
else if(n <= 389)
maxPrimes = n / 4;
else if(n <= 1139)
maxPrimes = n / 5;
else if(n <= 3121)
maxPrimes = n / 6;
else if(n <= 8479)
maxPrimes = n / 7;
else
maxPrimes = n / 8;

int[] primes = new int[maxPrimes]; //Hier speichern wir uns alle bisher gefundenen Primzahlen

int numPrimes = 0; //Hier speichern wir uns wie viele Primzahlen wir bisher gefunden haben

//die Zahlen 2 bis n durchlaufen und sie auf Primzahlen überprüfen (1 lassen wir weg da Sie per definition keine Primzahl ist)
for(int toCheck = 2; toCheck <= n; toCheck++){

boolean dividerFound = false; //Hier speichern wir uns ob wir für die aktuelle Zahl (toCheck) einen Teiler gefunden haben
for(int z = 0; z < numPrimes; z++){ //alle bisher gefunden Primzahlen durchlaufen und überprüfen ob sie Teiler von toCheck sind

if(primes[z] > toCheck / 2) //falls die Primzahl grösser als die hälfte von toCheck ist kann sie kein Teiler mehr sein und wir sind fertig
break;

if( toCheck % primes[z] == 0 ){ //Falls der Rest 0 ist haben wir einen Teiler von toCheck gefunden...
dividerFound = true; //...damit haben wir einen Teiler gefunden und...
break; //...wir können die Schleife verlassen.
}
}

if(!dividerFound){ //Falls wir keinen Teiler gefunden haben ist toCheck eine Primzahl
System.out.println(toCheck); //Primzahl ausgeben
primes[numPrimes] = toCheck; //Primzahl zu den schon gefunden Primzahlen hinzufügen
numPrimes = numPrimes + 1; //Anzahl der gefundenen Primzahlen erhöhen
}
}
}
}
</pre>

Optimierter Primzahlenfinder - optionale Aufgabe
<pre>
class PrimeNumbersBOptional{

public static void main(String[] args){
int n = 10000; //Wir suchen alle Primzahlen zwischen 1 und n

int numPrimes = 0; //Hier speichern wir uns wie viele Primzahlen wir bisher gefunden haben

//die Zahlen 2 bis n durchlaufen und sie auf Primzahlen überprüfen (1 lassen wir weg da Sie per definition keine Primzahl ist)
for(int toCheck = 2; toCheck <= n; toCheck++){

boolean dividerFound = false; //Hier speichern wir uns ob wir für die aktuelle Zahl (toCheck) einen Teiler gefunden haben

for(int z = 2; z < toCheck / 2; z++){ //alle Zahlen kleiner als die hälfte von toCheck überprüfen

if( toCheck % z == 0 ){ //Falls der Rest 0 ist haben wir einen Teiler von toCheck gefunden...
dividerFound = true; //...damit haben wir einen Teiler gefunden und...
break; //...wir können die Schleife verlassen.
}
}

if(!dividerFound) //Falls wir keinen Teiler gefunden haben ist toCheck eine Primzahl
numPrimes = numPrimes + 1; //Anzahl der gefundenen Primzahlen erhöhen

System.out.println("Verhältniss " + toCheck + " zu " + numPrimes + ": " + toCheck/numPrimes); //Verhältniss von überprüften Zahlen zu gefundenen Primzahlen ausgeben
}
}
}
</pre>

← Nächstältere Version		Version vom 9. März 2009, 08:53 Uhr
Zeile 115:		Zeile 115:
	}		}
	</pre>		</pre>
		+
		+	[[Kategorie:Java_Loesungen]]

Javakurs 2007/Primzahlen/Lösungsvorschlag - Versionsgeschichte

Bmay: In Kategorie eingeordnet

Ghandi: init