Primzahlen berechnen

Dear visitor, welcome to Coder Forum. If this is your first visit here, please read the Help. It explains in detail how this page works. To use all features of this page, you should consider registering. Please use the registration form, to register here or read more information about the registration process. If you are already registered, please login here.

cheater

Trainee

Posts: 13

Tuesday, January 29th 2008, 5:22pm

Primzahlen berechnen

Hallo!!

Ich soll im Zuge eines Gemeinschaftsprojektes mithilfe vom Programm BlueJ(Java)

ein Programm bze. eine Methode schreiben die bei Eingabe einer Zahl überprüft ob es sich um eine Primzahl handelt.Leider hab ich keinen Plan wie der entsprechende code aussehen muss!!

Könnte mir bitte jemand behilflich sein

Danke

Torben Brodt

Administrator

Posts: 8,454

Tuesday, January 29th 2008, 6:47pm

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.

Latest blogs: Neuer EX4 Server, Java EE Summit im Juni in München, Kostenlos zur Cebit + Windows 8 Entwickler Schulung

/etc/shadow

Trainee

Posts: 18

Tuesday, January 29th 2008, 9:52pm

Java Quellcode

boolean tester(int n) {
int counter = 2;
boolean value = true;
while(counter < n) {
if((n % counter) == 0) { value = false; }
counter++;
}
return value;
}

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

SeBa

Master

Posts: 1,134

Tuesday, January 29th 2008, 10:23pm

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.

cheater

Trainee

Posts: 13

Wednesday, January 30th 2008, 8:33am

Lösung Primzahl berechnen

Danke für eure Hilfe!!

Funktioniert einwandfrei.

Max123

Professional

Posts: 444

Wednesday, January 30th 2008, 10:32am

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

/etc/shadow

Trainee

Posts: 18

Wednesday, January 30th 2008, 10:52am

es kommt dann sowas raus ..

Java Quellcode

boolean tester(int n) {
int counter = 2;
boolean value = true;
while((int)(counter/2) < n) {
if((n % counter) == 0) { 
       value = false; 
       counter = n;
       }
counter++;
}
return value;
}

SeBa

Master

Posts: 1,134

Wednesday, January 30th 2008, 11:17am

Wohl eher so:

Java Quellcode

boolean tester(int n) {
 int counter = 2;
 int n_halbe = n/2; 
 boolean value = true;
 while((counter < n_halbe) && (value)) {
  if((n % counter) == 0)  
       value = false; 
  counter++;
 }
 return value;
}

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)

/etc/shadow

Trainee

Posts: 18

Wednesday, January 30th 2008, 9:09pm

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

CansasCity

Beginner

Posts: 1

Friday, July 17th 2009, 7:08pm

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

http://de.wikipedia.org/wiki/Sieb_des_Eratosthenes

Erforder aber relativ viel Speicher

lg

ButAlive

Trainee

Posts: 26

Friday, July 17th 2009, 11:04pm

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].

Java Quellcode

public static final boolean isProbablePrime(int value)
{
   BigInteger v = new BigInteger(String.valueOf(value));
   return v.isProbablePrime(100);
}

grüße
ButAlive

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

SeBa

Master

Posts: 1,134

Sunday, July 19th 2009, 10:40am

Quoted from "CansasCity"

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

http://de.wikipedia.org/wiki/Sieb_des_Eratosthenes

Erforder aber relativ viel Speicher

lg

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.

Rondrer

Professional

Posts: 306

Sunday, July 19th 2009, 11:50am

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.

SeBa

Master

Posts: 1,134

Monday, July 20th 2009, 8:20pm

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?

Rondrer

Professional

Posts: 306

Monday, July 20th 2009, 8:36pm

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

SeBa

Master

Posts: 1,134

Wednesday, July 22nd 2009, 7:33pm

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.

DarthMaul

Intermediate

Posts: 126

Thursday, July 23rd 2009, 7:10pm

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