Java Programm für Primzahlen

Question

May 14, 2010, 02:48 AM

Java Programm für Primzahlen

Proble

In diesem Projekt schreiben Sie ein Java-Programm, das eine positive ganze Zahl n aus der Standardeingabe liest und dann die ersten n Primzahlen ausgibt. Wir sagen, dass eine ganze Zahl m durch eine ganze Zahl d ungleich Null teilbar ist, wenn es eine ganze Zahl k gibt, so dass m = k d ist, d. H. Wenn sich d gleichmäßig in m teilt. Entsprechend ist m durch d teilbar, wenn der Rest von m bei (ganzzahliger) Division durch d Null ist. Wir würden dies auch ausdrücken, indem wir sagen, dass d ein Teiler von m ist. Eine positive ganze Zahl p heißt Primzahl, wenn ihre einzigen positiven Teiler 1 und p sind. Die einzige Ausnahme von dieser Regel ist die Zahl 1 selbst, die als Nicht-Primzahl betrachtet wird. Eine positive ganze Zahl, die keine Primzahl ist, wird als zusammengesetzt bezeichnet. Euklid hat gezeigt, dass es unendlich viele Primzahlen gibt. Die Prim- und Composite-Sequenzen beginnen wie folgt:

Primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, … 

Composites: 1, 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, …

Es gibt viele Möglichkeiten, eine Zahl auf ihre Ursprünglichkeit hin zu testen. Am einfachsten ist es jedoch, einfach eine Teilung zu versuchen. Beginnen Sie, indem Sie m durch 2 teilen, und wenn es sich gleichmäßig teilt, ist m keine Primzahl. Andernfalls teilen Sie durch 3, dann 4, dann 5 usw. Wenn sich herausstellt, dass m an einem beliebigen Punkt durch eine Zahl d im Bereich von 2 d m - 1 teilbar ist, halten Sie an und schließen Sie, dass m zusammengesetzt ist. Andernfalls schließen Sie, dass m Primzahl ist. Der Gedanke eines Augenblicks zeigt, dass man keine Versuchsteilung durch die Zahlen d machen muss, die selbst zusammengesetzt sind. Wenn beispielsweise eine Versuchsteilung durch 2 fehlschlägt (d. H. Einen Rest ungleich Null hat, also m ungerade ist), muss auch eine Versuchsteilung durch 4, 6 oder 8 oder eine beliebige gerade Zahl fehlschlagen. Um also eine Zahl m auf Primalität zu testen, muss man nur eine Teilung durch Primzahlen unter m versuchen. Darüber hinaus ist es nicht notwendig, bis zu m − 1 zu gehen. Es ist nur eine Probeteilung von m durch Primzahlen p im Bereich von 2 um erforderlich. Angenommen, m> 1 ist zusammengesetzt. Dann existieren positive ganze Zahlen a und b, so dass 1 <a <m, 1 <b <m und m = ab. Aber wenn sowohl a> m als auch b> m, dann ab> m, was im Widerspruch zu m = ab steht. Daher muss eines von a oder b kleiner oder gleich m sein.

Um diesen Prozess in Java zu implementieren, schreiben Sie eine Funktion namens isPrime () mit der folgenden Signatur:

static boolean isPrime(int m, int[] P)

Diese Funktion gibt je nachdem, ob m eine Primzahl oder eine zusammengesetzte Zahl ist, "true" oder "false" zurück. Das Array-Argument P enthält eine ausreichende Anzahl von Primzahlen, um den Test durchzuführen. Zum Zeitpunkt des Aufrufs von isPrime () muss das Array P (mindestens) alle Primzahlen p im Bereich von 2 μm enthalten. Um zum Beispiel m = 53 auf Primalität zu testen, muss man aufeinanderfolgende Versuchsunterteilungen durch 2, 3, 5 und 7 durchführen. Wir gehen nicht weiter, da 11> 53. Voraussetzung für den Funktionsaufruf isPrime (53, P) ist also, dass P [0] = 2, P [1] = 3, P [2] = 5 und P [3] = 7. Der Rückgabewert wäre in diesem Fall wahr, da alle diese Unterteilungen fehlschlagen. Ähnlich wie bei Test m = 143 muss man eine Teilung nach 2, 3, 5, 7 und 11 durchführen (da 13> 143). Voraussetzung für den Funktionsaufruf isPrime (143, P) ist daher P [0] = 2, P [1] = 3, P [2] = 5, P [3] = 7 und P [4] = 11. Der Rückgabewert wäre in diesem Fall falsch, da 11 Teilungen 143 sind. Die Funktion isPrime () sollte eine Schleife enthalten, die das Array P schrittweise durchläuft und Probeteilungen durchführt. Diese Schleife sollte enden, wenn 2 entweder eine Testdivision erfolgreich ist, in welchem Fall false zurückgegeben wird, oder bis die nächste Primzahl in P größer als m ist, in welchem Fall true zurückgegeben wird. Die Funktion main () in diesem Projekt liest das Befehlszeilenargument n, weist ein int-Array der Länge n zu, füllt das Array mit Primzahlen und druckt den Inhalt des Arrays gemäß dem unten beschriebenen Format auf stdout. Im Kontext von function main () werden wir dieses Array als Primes [] bezeichnen. Somit spielt Array Primes [] in diesem Projekt eine doppelte Rolle. Zum einen werden damit die Ausgabedaten gesammelt, gespeichert und gedruckt. Andererseits wird es an die Funktion isPrime () übergeben, um neue Ganzzahlen auf Primalität zu testen. Immer wenn isPrime () true zurückgibt, wird die neu entdeckte Primzahl an der entsprechenden Position im Array Primes [] platziert. Dieser Prozess funktioniert, da, wie oben erläutert, die Primzahlen, die zum Testen eines ganzzahligen m-Bereichs erforderlich sind, nur bis zu m reichen und alle diese Primzahlen (und mehr) bereits in Array-Primes [] gespeichert werden, wenn m getestet wird. Natürlich müssen Sie Primes [0] = 2 manuell initialisieren und dann 3, 4,… mit der Funktion isPrime () auf Primalität prüfen.

Das Folgende ist eine Übersicht über die in function main () auszuführenden Schritte.

Überprüfen Sie, ob der Benutzer genau ein Befehlszeilenargument angegeben hat, das als positive Ganzzahl n interpretiert werden kann. Wenn das Befehlszeilenargument keine einzelne positive Ganzzahl ist, gibt Ihr Programm eine Verwendungsmeldung aus, wie in den folgenden Beispielen angegeben.Allocate array Primes [] der Länge n und initialize Primes [0] = 2.Geben Sie eine Schleife ein, die nachfolgende Primzahlen erkennt und als Primzahlen [1], Primzahlen [2], Primzahlen [3], ..., Primzahlen [n −1] speichert. Diese Schleife sollte eine innere Schleife enthalten, die aufeinanderfolgende ganze Zahlen durchläuft und sie auf ihre Primalität prüft, indem die Funktion isPrime () mit den entsprechenden Argumenten aufgerufen wird.Drucken Sie den Inhalt des Arrays Primes [] bis stdout, 10 in eine durch einzelne Leerzeichen getrennte Zeile. Mit anderen Worten, Primes [0] bis Primes [9] gehen in Zeile 1, Primes [10], Primes [19] gehen in Zeile 2 und so weiter. Beachten Sie, dass die letzte Ausgabezeile weniger als 10 Primzahlen enthält, wenn n kein Vielfaches von 10 ist.

Ihr Programm, das Prime.java heißt, erzeugt eine Ausgabe, die mit der der folgenden Beispielläufe identisch ist. (Wie üblich bedeutet% die Unix-Eingabeaufforderung.)

% java Prime 
Usage: java Prime [PositiveInteger] 
% java Prime xyz 
Usage: java Prime [PositiveInteger] 
% java Prime 10 20 
Usage: java Prime [PositiveInteger] 
% java Prime 75 
2 3 5 7 11 13 17 19 23 29 
31 37 41 43 47 53 59 61 67 71 
73 79 83 89 97 101 103 107 109 113 
127 131 137 139 149 151 157 163 167 173 
179 181 191 193 197 199 211 223 227 229 
233 239 241 251 257 263 269 271 277 281 
283 293 307 311 313 317 331 337 347 349 
353 359 367 373 379 
% 
3

Wie Sie sehen können, erzeugen unangemessene Befehlszeilenargumente eine Verwendungsmeldung, die der vieler Unix-Befehle ähnelt. (Versuchen Sie, den Befehl more ohne Argumente auszuführen, um eine solche Meldung anzuzeigen.) Ihr Programm enthält eine Funktion namens Usage () mit der Signatur

static void Usage()

that gibt diese Nachricht an stderr aus und wird dann beendet. Somit enthält Ihr Programm insgesamt drei Funktionen: main (), isPrime () und Usage (). Jedem sollte ein Kommentarblock vorangestellt werden, in dem der Name, eine kurze Beschreibung der Funktionsweise und alle erforderlichen Voraussetzungen (z. B. für isPrime ()) angegeben sind. Siehe Beispiele auf der Webseite.

Versuchte Lösung

class Prime {
    public static void main(String[] args) {
        int num1 = 0;
        int num2 = 0;
        int num3;
        for (num1 = 1; num1 < 101; num1++)
            System.out.println(num1);
        for (num2 = 1; num2 < 101; num1++)
            System.out.println(num2);
        num3 = num2 % num1;
        if (num3 == 0)
            System.out.println("The prime numbers are " + num1);
        else
            System.out.println("The prime numbers are " + (num1 += 1));
    }
}