damit kann man sich sowohl in der fortgeschrittenen Informatik als auch in der Schule befassen...
wie hättest du es denn gerne? BlueJ deutet auf Anfänger?

Der einfachste Algorithmus ist, dass du eine Schleife begonnen bei 2 bis zu deiner Zahl läufst und prüfst ob deine Zahl dadurch teilbar ist.

wenn value true ist, dann ist deine zahl eine primzahl.

Hey Leute, wieviele Zahlen soll es denn bitte geben die n ganzzahlig teilen und größer sind als n/2. Man kann die Laufzeit der Schleife also beruhigt um die Hälfte reduzieren. Je nach Größenordnung eine nicht ganz unerheblich Zeitspanne.

Noch besser ist es, wenn man die Schleife auch abbricht, sobald man einen Gegenbeweis gefunden hat.

es kommt dann sowas raus ..

Wohl eher so:



Wieso teilst du denn Counter durcfh 2. Das verkürzt die Schleife doch überhaupt nicht, eher im Gegenteil, sie läuft doppelt solange und du testest auch Werte die größer sind als n. WENN ÜBERHAUPT müsste es counter *2 heißen, aber aus Performancegründen hab ich die Berechnung eh aus der Schleife rausgenommen, damit sie nicht jedesmal gemacht werden muss, das würde bei der Mulitiplikation aber nicht gehen. Ich glaub den Typecast hättest du auch nicht gebraucht. Auch der Abbruch indem du counter hochsetzt ist etwas merkwürdig, bei Zählschleifen versuche ich die Zählvariable möglichst so zu lassen wie sie ist, dann schon lieber ein break, da sieht man das wenigstens sofort. Aber das braucht man beides nicht, wir haben ja eh eine Variable dafür (value)

ups, ich meinte oben n/2 und nicht counter/2

Das ist der mir bekannte, schnellste Algorithmus für Primzahlen:

de.wikipedia.org/wiki/Sieb_des_Eratosthenes

Erforder aber relativ viel Speicher

lg

Hallo,
Es gibt im JDK eine Möglichkeit zu testen ob eine Zahl eine Primzahl ist, die Wahrscheinlichkeit das es wahr ist liegt dabei aber nicht bei 100%. Du kannst angeben wie hoch die Wahrscheinlichkeit sein soll, dabei berechnet sich die Wahrscheinlichkeit mit 1-1/(2^parameter) also je höher der Parameter ist desto wahrscheinlicher ist es, dass die Zahl wirklich eine Primzahl ist. Wie der Algorithmus genau funktioniert hab ich jetzt keine Lust zu erklären, wenn es dich interessiert, kannst du bei wikipedia unter Miller-Rabin-Test nachschauen[1].



grüße
ButAlive

[1] de.wikipedia.org/wiki/Miller-Rabin-Test

Sieb des Erasthotenes ist dafür da um alle Primzahlen in einem Intervall zu finden, aber nicht um zu testen ob eine Zahl eine Primzahl ist. Das kann man dann letzendlich auch damit machen indem man alle gefundenen Primzahlen durchgeht, aber ich glaube nicht, dass das schneller ist als andere Verfahren.

Das Sieb ist schon verdammt schnell, da es keinerlei Multiplikationen oder Divisionen enthält. Natürlich ist es nicht sinnvoll zum Prüfen einer einzigen Zahl den Sieb anzuwenden und alle Primzahlen zu berechnen die kleinergleich der gesuchten Zahl sind und dann zu Prüfen ob die gesuchte Zahl in der Ergebnismenge ist.
Man kann aber beide Verfahren kombinieren und die Primzahlen bis zur Wurzel der gesuchten Zahl (das reicht übrigens auch bei der "normalen ausprobier-Methode" bis zur Wurzel zu gehen und nicht bis n/2) mittels Sieb erzeugen und für diese dann prüfen ob sie Teiler der gesuchten Zahl sind.

Das mit der Wurzel stimmt, daran hatte ich nicht gedacht. Dass das Sieb schnell ist hab ich nicht abgestritten, aber zum Suchen ungünstig. Die Kombination aus beiden Verfahren hab ich jetzt nicht verstanden... Kannste mir nochmal erklären wie man da weniger als Wurzel(n) Zahlen prüfen kann?

Naja man prüft einfach nur die Primzahlen bis Wurzel n, statt alle Zahlen bis Wurzel n. Und die findet man mit dem Sieb.

Achso ja klar, das kann besser sein, muss aber nicht. Extrembeispiel: 4592043265702436502, es würde sicher länger dauern alle Primzahlen zu berechnen, die in dem Intervall liegen um dann rauszufinden, zwei ist Teiler der Zahl, als wenn da die Schleife mit Abbruchbedingung macht. Es hängt von dem Kontext der Anwendung ab. Wie groß sind die Zahlen die da so im Schnitt getestet werden und handelt es sich öfter wirklich um Primzahlen oder nicht.

ich hab mich zwar nicht weiter mit dem thema beschäftigt, aber die java-entwickler machen auch unterscheidungen:
z.b. hab ich mir mal den code der klasse array angeschaut, die ja methoden zum sortieren bereitstellt.
da wird auch geprüft, ob die zahl größer oder kleiner 7 ist, und dann jeweils sortiert.
so als kleine anregung

mfg