Die Welt der Primzahlen - Algorithmen

Der einfachste Algorithmus zum Feststellen, ob eine Zahl eine Primzahl ist, ist der folgende:
Nehmen wir an, eine Zahl i ist zu prüfen. Dann durchlaufen wir alle Zahlen j, die kleiner als i sind und prüfen, ob i ganzzahlig ohne Rest durch j teilbar ist. Sobald ein j gefunden ist, für welches dies gilt, ist i keine Primzahl; ansonsten ist i eine Primzahl.
In Java-Source-Code ausgedrückt, kann man dies wie folgt schreiben:
public class CalcPrimeNumbers {
	
	public static void main(String[] args) {
		
		// Bis zu dieser Grenze sollen die 
		// Primzahlen berechnet werden
		int max = 100;
		
		System.out.println ("Die Zahl 2 ist eine Primzahl.");
		
		// Wir starten mit der Berechnung bei 3,
		// da 1 keine Primzahl ist und wir 2 schon
		// gerade ausgegeben haben
		for (int i = 3; i <= max; i++)
		{
			boolean istPrimzahl = true;
			
			int j = 2;
			
			// Wir müssen nur bis i/2 prüfen, da größere
			// Zahlen kein Teiler mehr sein können.
			while (istPrimzahl && j <= (i/2))
			{
				// Wenn es eine Zahl j gibt, durch die i
				// ganzzahlig teilbar ist, dann ist i keine
				// Primzahl
				if ((i % j) == 0)
				{
					istPrimzahl = false;
				}
				
				// Für den nächsten Schleifendurchlauf
				j++; 
			}
			
			System.out.print("Die Zahl "+i+" ist ");
			
			if (istPrimzahl)
			{
				System.out.print("eine");
			}
			else
			{
				System.out.print("keine");
			}
			
			System.out.println(" Primzahl.");
		}
	}
}

Powered by: