Primzahlen_tester

[Xaver code]

Hallo,
ich schreibe gerade einen primzalen tester für einen freund ich komme aber nicht weiter da egal welche zahl eingebe es wird immer ausgegeben das es eine priemzahl ist

package Priemzahlen_tester;

public class Main {

    public static void main(String[] args) {
       
        int number = 4;
       
        if(number / number == 1 && number / 1 == number) {
            System.out.println(number + " ist eine Priemzahl");
        } else if(number / number != 1 && number / 1 != number) {
            System.out.println(number + " ist keine Priemzahl");
        }
       

    }

}

das ist mein code würde mich über Hilfe freuen.

ps.: falls sehr offensichtliche Fehler drin sind ich bin noch Anfänger.
LG

 

[LimDul]

ps.: falls sehr offensichtliche Fehler drin sind ich bin noch Anfänger.

Nun ja, der Code hat nun mal nichts mit einem Primzahltester zu tun.
Du testest, ob eine Zahl geteilt durch selber 1 ergibt und ob eine Zahl geteilt durch 1 sich selber ergibt, dann behauptest du, das ist ein Primzahl.

4 ist laut deinem Code also eine Primzahl, wenn 4/4 = 1 und 4/1 = 4 ergibt. Was nun mal nicht stimmt

Wirf den weg und schreib erst mal auf, wie das funktionieren soll. Wann ist eine Zahl eine Primzahl? Erstmal ganz simpel formulieren und dann als Code umsetzen.

 

[Robert Zenz]

ps.: falls sehr offensichtliche Fehler drin sind ich bin noch Anfänger.

Fangen wir damit an dass du augenscheinlich nicht weiszt was eine Primzahl ist. Eine Primzahl ist eine Zahl welche nur durch sich selbst oder Eins teilbar ist. Soweit so gut. Das bedeutet um festzustellen ob dies eine Primzahl ist, muss man ausschlieszen dass die Zahl durch irgendeine andere Zahl teilbar ist als durch sich selbst und Eins.

Du testest im Moment ob die gegebene Zahl durch sich selbst und durch Eins teilbar ist...das ist aber jede Zahl. Du musst pruefen ob sie auch durch andere teilbar ist. Beispiele als Wahrheitstabelle, "Spalte ist restlos teilbar durch Zeile":

    1  2  3  4  5  6  7  8  9
 1  J  J  J  J  J  J  J  J  J
 2  N  J  N  J  N  J  N  J  N
 3  N  N  J  N  N  J  N  N  J
 4  N  N  N  J  N  N  N  J  N
 5  N  N  N  N  J  N  N  N  N
 6  N  N  N  N  N  J  N  N  N
 7  N  N  N  N  N  N  J  N  N
 8  N  N  N  N  N  N  N  J  N
 9  N  N  N  N  N  N  N  N  J

Du suchst also nach Spalten/Zahlen welche nur zwei "J" haben, naemlich alle jene welche nur durch sich selbst oder Eins teilbar sind. Wie du merkst, sind alle Zahlen zumindest durch Eins und sich selbst teilbar. Und auf das musst du auch pruefen, ob die Zahl durch alle anderen nicht teilbar ist.

 

[Neumi5694]

Betonung auf "nur".
D.h. du musst alles andere ausschließen. Nur wenn die Zahl durch keine andere teilbar ist, ist sie eine Primzahl. Dein Algorithmus muss also so ziemlich genau das Gegenteil von dem machen, was er aktuell macht.
Als kleiner Tip: Abgesehen von den Spezialfällen am Anfang muss du nur Divisoren testen, die kleiner als die Wurzel deiner Zahl sind

 

[Xaver code]

Betonung auf "nur".
D.h. du musst alles andere ausschließen. Nur wenn die Zahl durch keine andere teilbar ist, ist sie eine Primzahl. Dein Algorithmus muss also so ziemlich genau das Gegenteil von dem machen, was er aktuell macht.
Als kleiner Tip: Abgesehen von den Spezialfällen am Anfang muss du nur Divisoren testen, die kleiner als die Wurzel deiner Zahl sind

also so wie ich es jetzt verstanden habe Muss ich also testen ob number / {irgendeine random zahl} teilbar ist. Also wenn number durch einer gerade und einer ungeraden zahl nicht teilbar ist dann ist das eine priemzahl ?
habe ich das so erstmal richtig verstanden?

 

[LimDul]

also so wie ich es jetzt verstanden habe Muss ich also testen ob number / {irgendeine random zahl} teilbar ist. Also wenn number durch einer gerade und einer ungeraden zahl nicht teilbar ist dann ist das eine priemzahl ?
habe ich das so erstmal richtig verstanden?

Nein. Wenn es außer 1 und selber keine weitere Zahl gibt, durch die sie teilbar ist. Das heißt, z.B. 57 ist genau dann ein Primzahl wenn sie nur durch 1 und 57 teilbar ist. Also musst du sicherstellen, dass nicht durch:
2,3,4,5,6,7,8,9,10,.....50,51,52,53,54,55,56 teilbar ist.

 

[mihe7]

Also musst du sicherstellen, dass nicht durch:
2,3,4,5,6,7,8,9,10,.....50,51,52,53,54,55,56 teilbar ist.

@Xaver code, dazu kann man sich ein paar Dinge überlegen. Zuerst: jede gerade Zahl ist durch 2 teilbar. Es kann also keine gerade Primzahl > 2 geben. Damit fallen die Teiler, die ein Vielfaches von 2 sind, schon mal weg. Der zweite Teil: die Multiplikation ist kommutativ: a*b=b*a. Daher reicht es, die Teiler bis zur Wurzel der Zahl zu untersuchen. Bei 57 müssten also nur die Teiler 2, 3, 5 und 7 überprüft werden.

 

[uuu3uuu]

Fun fact: Das Leben wäre auch sehr viel einfacher, wenn man sagen könnte, in welchen Abständen mögliche Teiler vorkommen...

Sprich: Bei Element aus [2,sqrt(x)] nicht alle (oder nicht die Hälfe) Elemente testen zu müssen

Btw: Java hat eine "is probable prime" Methode, die schon sehr gute Prognosen gestattet

 

[Neumi5694]

also so wie ich es jetzt verstanden habe Muss ich also testen ob number / {irgendeine random zahl} teilbar ist. Also wenn number durch einer gerade und einer ungeraden zahl nicht teilbar ist dann ist das eine priemzahl ?
habe ich das so erstmal richtig verstanden?

Nein, du musst sicherstellen, dass es durch keine dieser Zahlen teilbar ist.

@uuu3uuu alles richtig, aber bei Schulaufgaben geht man erst mal mit der Brute Force Methode vor.
Und es kann mir keiner erzählen, dass die Suche nach Primzahlen keine Schulaufgabe ist.

 

[Oneixee5]

@Xaver code, dazu kann man sich ein paar Dinge überlegen. Zuerst: jede gerade Zahl ist durch 2 teilbar. Es kann also keine gerade Primzahl > 2 geben. Damit fallen die Teiler, die ein Vielfaches von 2 sind, schon mal weg. Der zweite Teil: die Multiplikation ist kommutativ: a*b=b*a. Daher reicht es, die Teiler bis zur Wurzel der Zahl zu untersuchen. Bei 57 müssten also nur die Teiler 2, 3, 5 und 7 überprüft werden.

Eine ebenfalls einfach zu implementierende Optimierung berücksichtigt, daß alle Zahlen, die weder durch 2 noch durch 5 teilbar sind, zwangsläufig auch nicht durch alle größeren Zahlen teilbar sind, die mit 2,4,5,6,8 oder 0 enden. In der Schleife müssen also nach der zwei und der fünf nur noch diejenigen Teiler ausprobiert werden, die mit den Ziffern 1,3,7 und 9 enden.

 

[Oneixee5]

@Xaver code, dazu kann man sich ein paar Dinge überlegen. Zuerst: jede gerade Zahl ist durch 2 teilbar. Es kann also keine gerade Primzahl > 2 geben. Damit fallen die Teiler, die ein Vielfaches von 2 sind, schon mal weg. Der zweite Teil: die Multiplikation ist kommutativ: a*b=b*a. Daher reicht es, die Teiler bis zur Wurzel der Zahl zu untersuchen. Bei 57 müssten also nur die Teiler 2, 3, 5 und 7 überprüft werden.

Eine ebenfalls einfach zu implementierende Optimierung berücksichtigt, daß alle Zahlen, die weder durch 2 noch durch 5 teilbar sind, zwangsläufig auch nicht durch alle größeren Zahlen teilbar sind, die mit 2,4,5,6,8 oder 0 enden. In der Schleife müssen also nach der zwei und der fünf nur noch diejenigen Teiler ausprobiert werden, die mit den Ziffern 1,3,7 und 9 enden.

 

[Neumi5694]

Eine ebenfalls einfach zu implementierende Optimierung berücksichtigt, daß alle Zahlen, die weder durch 2 noch durch 5 teilbar sind, zwangsläufig auch nicht durch alle größeren Zahlen teilbar sind, die mit 2,4,5,6,8 oder 0 enden. In der Schleife müssen also nach der zwei und der fünf nur noch diejenigen Teiler ausprobiert werden, die mit den Ziffern 1,3,7 und 9 enden.

So was ähnliches wollte ich auch schon schreiben. Das ist allerdings nur ein theoretischer Ansatz, die Laufzeit wird daduch sogar verlängert.

Durch 2,3,5 testet man ja gleich am Anfang, die höheren Divisoren werden beim Durchlaufen der Schleife gar nicht erst erreicht.
Eine einfache mod-Operation ist weniger rechenintensiv als die Zahl zuerst mal im Zehnersystem darzustellen und die letzte Ziffer rauszupicken.


Falls man eine Liste aller Primzahlen erstellen und pro Zahl die Tests parallel laufen lassen will, reicht es natürlich, nur durch die bisher bekannten Primzahlen zu dividiern.

 

[Oneixee5]

So was ähnliches wollte ich auch schon schreiben. Das ist allerdings nur ein theoretischer Ansatz, die Laufzeit wird daduch sogar verlängert.

Durch 2,3,5 testet man ja gleich am Anfang, die höheren Divisoren werden beim Durchlaufen der Schleife gar nicht erst erreicht.
Eine einfache mod-Operation ist weniger rechenintensiv als die Zahl zuerst mal im Zehnersystem darzustellen und die letzte Ziffer rauszupicken.


Falls man eine Liste aller Primzahlen erstellen und pro Zahl die Tests parallel laufen lassen will, reicht es natürlich, nur durch die bisher bekannten Primzahlen zu dividiern.

Naja, ich würde hier ja einen Test rein stellen aber dieser würde die komplette Hausaufgabe lösen

 

[uuu3uuu]

Naja, ich würde hier ja einen Test rein stellen aber dieser würde die komplette Hausaufgabe lösen

Geht mir ähnlich. Also Komplettlösungen gibt es hier nicht...