Warum berechnet mein Primzahlenprog zu hohe Zahlen nicht?

mancko

Mitglied
HI,


ich hab mir nen primzahlen checker gemacht... funzt super (ist aber wsl nicht die eleganteste Lösung - aber egal)

Jedenfalls bekomme ich ab ~2100000000 folgenden Fehlercode in Eclipse:

Code:
Prüfzahl: 2200000000
Exception in thread "main" java.util.InputMismatchException: For input string: "2200000000"
    at java.base/java.util.Scanner.nextInt(Scanner.java:2264)
    at java.base/java.util.Scanner.nextInt(Scanner.java:2212)
    at kartenspiel.prim3checker2.main(prim3checker2.java:15)



Ich vermute es hat was damit zu tun das ich int´s benutze oder? Da war mal was mit Speicherplatz Größen von Ints und co^^ des hab ich nie so recht verstanden 😀 Ist das hier das Problem? muss ich das jetzt lernen?^^



Hier mein Prog:


Java:
package kartenspiel;

import java.util.Scanner;

public class prim3checker2 {
    public static void main(String[] args) {
        
        
    Scanner eingabewert = new Scanner(System.in);   
                
        
        
    System.out.print("Prüfzahl: ");
        int a;
        a = eingabewert.nextInt();
        
        System.out.print("Suche nach Teilern für "+a+" ohne Restwert: ");
                int b = a;
                int ac;
                int ax;  //wohl teiler
                int p = 0;   //zähler, wird erhöht wenn nenner durch zähler teilbar ist ohne rest
                            
                                
                while (a == b) { //während a gleich b ist tue:
                        ac = a;   
                        ax = a;
                    
                                        
                        
                        while (ax >= 1) {                                             //Whärend ax größer gleich 1 ist, tue:                               
                                        
                                if (ac % ax == 0 && ax != ac && ax != 1) { p++;         //WENN  Rest von ac druch ax null ist    UND    ac NICHT GLEICH ax ist    UND  ax nicht gleich 1 ist  P+1
                                System.out.print(ax +", ");     }       
                                                                                        // ALSO    Zahl ist ohen rest teilbar   und   aber nicht durch sich selber   und nicht durch 1   P+1
                                if (ax == 1 && p >= 1) { System.out.println("fertig.");}  //damit nach aufzählung der teilern nicht ein Komma steht.
                                if (ax == 1 && p == 0) { System.out.println(" ...keine Teiler ohne Rest gefunden.");}  //WENN ax 1 ist UND P 1 ist   (WSL ÜBerflüssig)
                                                    
                                    ax--;   //ax minus eins TEILER
                
                                        } // ende erste whileschleife
                            
                b++;   //erhöhe b damit erste schleife beendet wird
            }  //ende zweiute schleife
                
                
        System.out.println(" ");
        System.out.println(a + " ist neben 1 und sich selbst durch "+p + " Zahlen teilbar.");
        
        
        if (p >= 1) {System.out.println("Daher ist "+ a+ " KEINE Primzahl...");
        } else { System.out.println("Somit ist "+a+ " eine Primzahl!");}   
                
                        
    }
}

Danke für Infos 🙂
 
Der maximale Wert für ints in Java ist 2_147_483_647, dein 2_200_000_000 ist offensichtlich größer, kann deshalb nicht als int gelesen werden 😉

Größere Werte wären mit long möglich, noch größere dann mit BigInteger.
 
Cool THX! 🙂
BigInteger hat irwie nicht geklappt, da muss ich dann wohl was im code umstellen...

mit long sucht mein HighEndPC jetzt schon seit 10 min nach Teilern für 99.999.999.999.999^^

Danke 🙂
 
Mein LowEndLaptop denkt hier kaum nach:

Java:
import java.util.StringJoiner;
import java.math.BigDecimal;

public class Test {

    public static void main(String[] args) {
        long value = 99_999_999_999_999L;
        long max = (long) Math.sqrt((double) value);

        StringJoiner j = new StringJoiner(", ");

        for (long i = 3; i <= max; i += 2) {
            if (value % i == 0) {
                j.add(String.valueOf(i));
            }
        }

        System.out.printf("Teiler von %d: %s\n", value, j.toString());
    }
}
 
ok cool 😀
wie gesagt... mein porg ist offensichtlich nicht sehr elegant/gut geschrieben 😀 deines verstehe ich kaum... so weit bin ich einfach noch nicht🙂

Lässt ihr solche Sachen in Eclipse laufen oder macht ihr das ( bzw längere Rechendinge) in der CMD? Ich frage, weil ich mich gefragt habe, ob die CMD wohl schneller wäre als Eclipse... hab kein jre installiert und habs daher noch nicht getestet...
 
deines verstehe ich kaum... so weit bin ich einfach noch nicht
LOL, Deines ist in meinen Augen ungefähr 200 x komplizierter 🙂

Mal kurz zur Erklärung: die 2 kann kein Teiler sein, weil die Zahl ungerade ist. Daher habe ich die anfängliche Prüfung darauf weggelassen. Es kommen nur ungerade Teiler in Frage, daher fange ich bei der 3 an und gehe in zweier Schritten weiter. Man kann aufhören, wenn man die Quadratwurzel der betreffenden Zahl (sqrt = square root) erreicht hat.

In der Schleife prüfe ich einfach ab, ob sich value durch i teilen lässt. Falls ja, füge ich den Teiler zu einem StringJoiner hinzu. Dieses ist eine Klasse aus dem Paket java.util, die einfach nur die Aufgabe hat, eklige String-Konkatenationen mit Trennzeichen (also z. B. eine mit Komma separierte Liste) zu vereinfachen.

Am Ende gebe ich den Spaß noch aus und das wars.
 
Ah, daher hast du die 2 weggelassen. Hatte mich schon gewundert....

Wenn Du Teiler berechnen möchtest, dann könnte man Deinen Algorithmus erweitern:
a) Wenn etwas teilbar ist durch eine Zahl, dann könnte man prüfen, ob es mehrfach dadurch teilbar ist. Dann bekommst du nicht nur die Liste der Teiler sondern eine Primzahlen Zerlegung.

b) wenn es nur um Primzahl ja/nein geht, dann bricht man ab, sobald man einen Teiler hat. Wenn man alle Teiler haben möchte, dann kann man überlegen, die obere Grenze herab zu setzen (dein Max).

Aber das sind dann Optimierungen des Algorithmus.
 
Ah, daher hast du die 2 weggelassen. Hatte mich schon gewundert....

Wenn Du Teiler berechnen möchtest, dann könnte man Deinen Algorithmus erweitern:
a) Wenn etwas teilbar ist durch eine Zahl, dann könnte man prüfen, ob es mehrfach dadurch teilbar ist. Dann bekommst du nicht nur die Liste der Teiler sondern eine Primzahlen Zerlegung.

b) wenn es nur um Primzahl ja/nein geht, dann bricht man ab, sobald man einen Teiler hat. Wenn man alle Teiler haben möchte, dann kann man überlegen, die obere Grenze herab zu setzen (dein Max).

Aber das sind dann Optimierungen des Algorithmus.
Jap an sowas hatte ich auch schon gedacht... aber da ich nicht wusste wie hab ich erst mal das gemacht was ich bisher konnte^^
 
Das nutze ich jetzt gleich einmal zu einem kleinen Exkurs zu Optimierungen:
Ein wichtiger Grundsatz lautet: Keep It Simple, Stupid (KISS). Oder eben auch: Vermeide Optimierungen!

Was steckt dahinter?
Es geht darum, dass Code lesbar ist und bleibt. Und dass man die Anforderungen möglichst einfach/schnell/sicher erreicht. Daher wird nur das implementiert, das wirklich notwendig ist. Bei der Testbasierten Entwicklung (Test Driven Development TDD) ist es dann auch so, dass ein formulierter Test möglichst einfach erfüllt werden muss.

An der Uni wurde uns auch immer die 80/20 Regel genannt: 80% der Zeit hält sich eine Applikation in 20% seines Codes auf.

Wenn Du also hin gehst und einfach so optimierst, dann:
- wird der Code komplexer
- ist schwerer zu verstehen
- Fehler werden eher übersehen
- ist evtl. unnötig (was interessiert es mich, wenn einmal im Monat die Applikation 1s statt 2 oder 3 Sekunden braucht?.)
- ...

Klar, manchmal muss etwas schneller gehen. Aber dann muss hier auch eine genaue Analyse her. Ich optimiere dann nicht an einem Algorithmus herum sondern überlege mir Ggf. Generell etwas anderes. Ein Algorithmus, dessen Zeitbedarf in einer Potenz ansteigt, den kann ich um einen Faktor 10 verbessern: das bringt nichts, denn ich brauche eher einen Algorithmus, der sich linear entwickelt oder in log(n) oder gar konstant.... (Wenn so Komplexitäten, oft ausgedrückt mit O(n) unbekannt sind, dann ignorier diesen Abschnitt).

Als Aufgabe kann es interessant sein, etwas zu optimieren, aber bei der professionellen Softwareentwicklung ist es oft eher fehl am Platz.

Die Ideen sind natürlich valide, aber Primzahlen im Bereich eines Long: die berechne ich einmal und speichere sie, dann teste ich die Primzahl in log(n) Komplexität, denn ich kann z.B. einen binären, ausbalancierten Suchbaum bemühen....
Und zum Berechnen bemühe ich einen Großrechner mit tausenden von CPUs, der da dann auch nicht lange für brauchen dürfte ... (Ja, hab ich auch nicht im Keller, aber ich will nur aufzeigen: Nicht einfach optimieren, sondern Anforderung analysieren und dann überlegen, was wie möglich ist.)

Hoffe, das war jetzt nicht verwirrend ... aber ist mir eben auch durch den Kopf gegangen.
 
Mit 9223372036854775783L könntest Du testen. Das ist die größte PZ, die in ein long passt. Dauert bei mir ca 15 Sekunden.

Bei mir bisher mehrere Minuten... wsl kommt nichts mehr 😀 Mein code ist einfach nicht gut^^


Das nutze ich jetzt gleich einmal zu einem kleinen Exkurs zu Optimierungen:
Ein wichtiger Grundsatz lautet: Keep It Simple, Stupid (KISS). Oder eben auch: Vermeide Optimierungen!

Was steckt dahinter?
Es geht darum, dass Code lesbar ist und bleibt. Und dass man die Anforderungen möglichst einfach/schnell/sicher erreicht. Daher wird nur das implementiert, das wirklich notwendig ist. Bei der Testbasierten Entwicklung (Test Driven Development TDD) ist es dann auch so, dass ein formulierter Test möglichst einfach erfüllt werden muss.

An der Uni wurde uns auch immer die 80/20 Regel genannt: 80% der Zeit hält sich eine Applikation in 20% seines Codes auf.

Wenn Du also hin gehst und einfach so optimierst, dann:
- wird der Code komplexer
- ist schwerer zu verstehen
- Fehler werden eher übersehen
- ist evtl. unnötig (was interessiert es mich, wenn einmal im Monat die Applikation 1s statt 2 oder 3 Sekunden braucht?.)
- ...

Klar, manchmal muss etwas schneller gehen. Aber dann muss hier auch eine genaue Analyse her. Ich optimiere dann nicht an einem Algorithmus herum sondern überlege mir Ggf. Generell etwas anderes. Ein Algorithmus, dessen Zeitbedarf in einer Potenz ansteigt, den kann ich um einen Faktor 10 verbessern: das bringt nichts, denn ich brauche eher einen Algorithmus, der sich linear entwickelt oder in log(n) oder gar konstant.... (Wenn so Komplexitäten, oft ausgedrückt mit O(n) unbekannt sind, dann ignorier diesen Abschnitt).

Als Aufgabe kann es interessant sein, etwas zu optimieren, aber bei der professionellen Softwareentwicklung ist es oft eher fehl am Platz.

Die Ideen sind natürlich valide, aber Primzahlen im Bereich eines Long: die berechne ich einmal und speichere sie, dann teste ich die Primzahl in log(n) Komplexität, denn ich kann z.B. einen binären, ausbalancierten Suchbaum bemühen....
Und zum Berechnen bemühe ich einen Großrechner mit tausenden von CPUs, der da dann auch nicht lange für brauchen dürfte ... (Ja, hab ich auch nicht im Keller, aber ich will nur aufzeigen: Nicht einfach optimieren, sondern Anforderung analysieren und dann überlegen, was wie möglich ist.)

Hoffe, das war jetzt nicht verwirrend ... aber ist mir eben auch durch den Kopf gegangen.

Nein nicht verwirrend... logisch und ökonomisch 🙂 Ich kenne diese Grundsätze in Grundzügen aus BWL...
Wie gesagt 🙂 Ohne die entsprechenden Javakenntnisse war ein besserer Code leider erst mal nicht zu machen :/ Was 80% angeht^^ Ich hab so ca. 99,9% der Zeit für meinen aktuellen Code gebraucht 😀 ... Ich werd erst mal einiges lesen und dann das Prog von grundauf neu machen und versuchen deine Tipps zu befolgen 🙂
 
Eigentlich... Müsste ein WinFo oder anderer Bindestrich Informatiker auch einen optimalen Algo in akzeptabler, annehmbarer Zeit schreiben können... afaik.
 
LOL, also das mit den richtigen Algorithmen wählen ist schlicht eine Frage der Erfahrung. Klar, dem einen liegt es mehr und dem anderen weniger. Wer professionell Software entwickeln will, dem sollte sowas liegen, aber das gilt doch für jeden Beruf. Es sollte etwas sein, was einem liegt und an dem man wenigstens etwas Spaß hat. Man muss ja nur daran denken, wieviel Zeit man später Mitbauer Thematik zubringen wird.... wenn einem das nicht liegt, dann ist das eine blöde Sache in Bezug auf Zufriedenheit und so.... (Soll aber natürlich jeder so machen, wie er es für richtig hält!)

Und bezüglich Algorithmen: Bei der Software Entwicklung läuft es meist immer wieder auf die gleichen Algorithmen hinaus. Aus dem Grund wurden gewisse ‚Standards‘ entwickelt, auch als Pattern bezeichnet. Das sind also Lösungsvorschläge für diverse Situationen, die man dann einfach anwenden kann.

Und was man auch unterscheiden muss ist die eigentliche Entwicklung von Code und die Probleme der abgebildetes Domäne. Mathematische Probleme sind so ein Beispiel. Da muss man zur Not einen Experten dazu nehmen. (Bzw. in dem Bereich ist dann entsprechendes Knowhow Pflicht.) Schreib man eine Buchhaltungssoftware ... Da gibt es dann Gesetze und Vorschriften zu beachten und so. Also ohne fachliches Knowhow undenkbar.
 
Und doch passt es 1a, denn man muss als Software Entwickler nicht drüber nachdenken, wie man am Besten ermittelt, ob eine Zahl eine Primzahl ist. Und wenn man genau das wirklich haben wollte, dann würde man entsprechende Experten heranziehen, denn auch unser Wissen ist darüber minimal und es gibt Mathematiker, die sich intensiv damit beschäftigt haben.
 
Primzahlen schnell berechnen, ja da gibt es X Methoden 😀

An einen Ansatz kann ich mich noch erinnern.
Man erstelle ein Array in der Größe der Größten Zahl+1 die man prüfen will
Also Wichtig bei Prim[3] geht es um die Zahl 3 und nicht um die 4 <== einfach für die Lesbarkeit

Dann schreibt man in jedes Feld ein X

Nun löscht man die X wieder mit folgender Methode
Java:
for(long i=2; i<=maxZahl/2; i++)
    {           
        if Prim[i].equals("X") {
                for(long j=i; j<=maxZahl+1; j++) {
                        if (j%i==0) {
                            Prim[j]="";
                        }
                }
        }
    }
Überlegung dabei ist folgende
1.) Da 2 die kleinste Primzahl ist, kann also der größte Teiler einer Zahl die Hälfte dieser Zahl sein. Ergo muss ich auch nur bis zur Hälfte prüfen, da dann bereits alle "X" gelöscht sind, die keine Primzahl sind.
2.) Ich muss nicht jeden Teiler prüfen, sondern nur durch Primzahlen prüfen.
3.) Nach Beendigung der beiden Schleifen muss man nur noch Prüfen ob das Feld ein X enthält. Ist dies der Fall, so handelt es sich um eine Primzahl.

Hoffe ich habe jetzt im Code keinen Fehler drin. Ist schon etwas länger her, dass ich Programmiert habe^^
 
An einen Ansatz kann ich mich noch erinnern.
Du meinst den Sieb des Eratosthenes, mit dem man alle Primzahlen zwischen 2 und einer gegebenen Zahl ermitteln kann. Allerdings ist Dein Ansatz nicht besonders effizient 🙂

Erstens musst Du in der äußeren Schleife nicht bis zur Hälfte der größten Zahl gehen, sondern nur bis zur Wurzel (Kommutativgesetz der Multiplikation). Zweitens kannst Du in der inneren Schleife einfach alle Vielfachen von i streichen.

Dann noch ein kleiner Fehler: in der inneren Schleife musst Du nicht bis maxZahl+1 gehen (Du musst maxZahl+1 nicht wegstreichen, wenn Dich nur die Primzahlen bis maxZahl interessieren)

Nachtrag, weil ich es gerade gesehen habe: die innere Schleife darf i nicht streichen. Dafür kann nach dem if das i gleich als Primzahl ausgegeben werden.
 

Neue Themen


Zurück
Oben