Javakurs 2007/Primzahlen/Lösungsvorschlag

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

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

Optimierter Primzahlenfinder

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

Optimierter Primzahlenfinder - optionale Aufgabe

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