Java Primzahlen
Ich hänge an einem Problem in Java:
Angenommen ich gebe in einem Numberfield eine Zahl ein "x" diese ist in der regel sehr groß z.b. (1.000.000.000)... Wenn ich auf meinen Button drücke wird daraus die Wurzel gezogen... so weit so gut, aber ich möchte jetzt, dass mir das programm verrät welche zahl die nächst kleiner Primzahl ist.
Ich weiß, dass das mit dem Sieb des Eratosthenes möglich ist aber wie bewerkstellige ich das in java?
Liebe Grüße,
Christian Meyer
6 Antworten
Erstelle Dir zunächst die Function IsPrime(x).
(wie ceevee, ABER nicht bis x sondern bis sqrt(x)
und nicht Z++ sondern z+=2 für nur ungerade)
Nun durchsuchst Du alle ungeraden Vorgänger (x mod 2 >0)
und ohne 5 am Ende (x mod 5 >0)
Sobald IsPrime() true -> output
Test:
Prime(50847534)=999999937
Prime(50847535)=10^9+7
mehr dazu unter http://www.gerdlamprecht.de/Primzahlen.htm
Im Internet gibt’s genug Online-Rechner, oder soll das eine Hausaufgabe sein?
Genau so geht's wohl am besten, DH. Mein Sieb braucht bei 10^9 Zahlen insgesamt 953 MB, wenn man's ganz profimäßig mit einer Bitmaske macht, dann sinds nur noch um die 119 MB, Speicherplatz ist also bei heutigen Rechnern nicht mehr unbedingt das große Problem, allerdings kann man einige tausend Primzahlen mit diesem Algorithmus prüfen, bevor sich das Sieb rentiert.
Nein! Das ist Teil der Optimierung:
- einmalig aus der Eingegebenen Zahl eine ungerade machen
- dann n-=2 und ohne Mod 5
- dann Aufruf IsPrim(), wobei mit 3 gestartet wird und intern z+=2!
So muss nur 1 mal statt n/2 mal auf UNGERADE überprüft werden.
Ich habe es noch weiter optimiert und statt z+=2 mit Array-Muster z+=a[i]
gearbeitet
Beispiel: n= 2 * 10^10 = 20000000000
Ergebnis: prime(882206716)=19999999967
Darf man sich auch irgendwo angucken, wie du das Array-Muster generierst?
Wenn du weißt, wie es geht, musst du es alleine hinkriegen.
Wenn du nicht weißt, wie es geht, musst du uns das konkrete Problem sagen, sonst können wir dir auch nicht helfen.
ja, dann werde ich mal konkret! :)
Ich will eine Zahl X eingeben und dann will ich die nächst kleiner Primzahl. Als Beispiel X=10; Dann will ich das er mit 7 weiter rechnet und nicht mit allen Primzahlen die kleiner sind als 10, sondern nur mit der letzten Primzahl (7).
Da wäre es doch das klügste, wenn man bei 10 beginnt und ausrechnet ob sie einen teiler hat außer sich selbst und 1. Dann zur nächst kleiner Zahl 9 geht und wieder überprüft ob es sich um eine Prim handelt. Solange bis man halt dann zur nächsten Primzahl kommt.
Aber wie man das in Java macht weiß ich nicht :X und da bitte ich dich sehr um hilfe!
Teil dir die Aufgabe auf - kriegst du schon ein Eratosthenes-Sieb zusammen? Also ein Array oder eine Liste, wo jeweils angegeben ist, ob der Index eine Primzahl ist? (sieb[1] = false, sieb[2] = true, sieb[3] = true, sieb[4] = false, sieb[5] = true, sieb[6] = false....)
nein ich habe nur eine liste, wo alle primzahlen drin sind von 1 bis n;
aber da würde ein computer doch ewig brauchen darum mein vorschlag,
Da wäre es doch das klügste, wenn man bei z.b. 10 beginnt und ausrechnet ob sie einen teiler hat außer sich selbst und 1. Dann zur nächst kleiner Zahl 9 geht und wieder überprüft ob es sich um eine Prim handelt. Solange bis man halt dann zur nächsten Primzahl kommt.
weil ich habe zum teil zahlen, wie 7358 und dann von 2 anfangen zu rechnen macht doch kein sinn, wenn ich die nächst kleinere Primzahl suche.
darum meinte ich 7358 - 1 und damit halt ausrechnet ob die eine Primzahl ist? Das dann in einer Schleife solange bis er eine gefunden hat die maximal nur 2 teiler hat, weil alle geraden zahlen fallen ja prinzipiell sowieso weg :)
Oder habe ich da einen Denkfehler?
Dankeschön schonmal für die schnelle und gute hilfe :)
darum meinte ich 7358 - 1 und damit halt ausrechnet ob die eine Primzahl ist? Das dann in einer Schleife solange bis er eine gefunden hat die maximal nur 2 teiler hat, weil alle geraden zahlen fallen ja prinzipiell sowieso weg :)
Das wäre der simple (und langsame) Ansatz, der würde ungefähr so aussehen.
// x = zu pruefende Zahl
bool isPrim = true;
for(int z=2;z<x;z++)
{
if(x % z == 0) //% = Modulo - Es wird der Rest der Ganzzahldivision zurückgegeben, 10 % 3 = 1
{
isprim = false;
break;
}
}
return isprim;
Der Ansatz des Primsiebes ist eigentlich genau umgekehrt, du generierst dir vor deinem eigentlichen Programm das Sieb und hälst es während des Ablaufs im Speicher. Hier wäre der Code dafür: http://introcs.cs.princeton.edu/java/14array/PrimeSieve.java.html (Versuch unbedingt zu verstehen, was da gemacht wird!). Dort kannst du dann komfortabel das Array abfragen, eben beispielsweise isPrime[7357] und bekommst dann "true" oder "false" zurück. Wenn du die nächstniedrigere Primzahl von einer gegebenen Zahl suchst, dann musst du eben von deiner gegebenen Zahl herunterzählen, bis der Wert "true" wird.
Oder habe ich da einen Denkfehler?
Es macht schon Sinn, mit 2 zu rechnen anzufangen. Um die neben 7358 nächstkleinere Primzahl zu erkennen, mußt Du ja alle x-Werte: 7358, 7357, 7356, 7355, 7354, 7353 usw. nacheinander testen. Dazu mußt Du prüfen, ob sie außer 1 und sich selbst Teiler haben und dazu mußt Du immer die möglichen Teiler der Reihe nach ausprobieren. Um das zeitsparend zu tun, solltest Du:
- Erstens nur die Primzahlen zwischen 2 und Wurzel aus x als Teiler ausprobieren. (Existiert kein Teiler bis maximal zur Wurzel, dann gibt es oberhalb der Wurzel auch keinen.)
- Zweitens mit den kleinen Teilerkandidaten beginnen, also mit 2, 3, 5, 7 usw. Denn die kleineren sind mit größerer Wahrscheinlichkeit als die großen tatsächlich Teiler und je schneller das Programm einen Teiler gefunden hat, um so schneller kann es zum nächsten x weitergehen.
Berechne also in einem vorbereitenden Arbeitsschritt mit dem Sieb des Eratosthenes eine Tabelle aller Primzahlen bis zur Wurzel des größten x-Wertes, mit dem Du arbeiten willst. Teste dann bei jedem x, mit 2 beginnend bis zur Wurzel aus x, die Primzahlen durch, ob sie x teilen, und geh, sobald ein Teiler gefunden ist, zum nächstkleineren x weiter. Tu das so lange, bis ein x gefunden ist, das keinen Teiler hat. Das ist dann die gesuchte Primzahl.
Moment, willst du damit sagen, dass ich alle primzahlen vor ab generieren soll und die dann im speicher halte?
Das programm generiert ja prinzipiell schonmal alle primzahlen
http://de.wikibooks.org/wiki/Primzahlen:_Programmbeispiele#Java
und du meinst ich soll die zwischenspeichern später dann abfragen? Vielleicht kannst du ja noch ein paar worte mehr zu deiner idee und dem skript verlieren, damit ich das besser nachvollziehen kann, vielen dank schonmal bis dahin!!! :)
ja gut dann verwerfe ich den gedanken und beginne lieber bei 2, berrechne alle prim bis zu meinem limit x und checke rückwirkend ab, welche die nächst gelegene primzahl ist?
http://de.wikibooks.org/wiki/Primzahlen:_Programmbeispiele#Java
über dieses script werden ja schonmal alle primzahlen errechnet, wie schaffe ich es dann, das er rückwirkend die nächst kleinere mir ausgibt? :)
auch dir ein riesen dankeschön bis dahin! :)
ich würde nen ähnlichen ansatzt wie ceevee wählen.
nur das ich die hälfte oberhalb von x und die unterhalb von x nach primzahlen durchforsten (leichte abänderung von ceevees code) und die beiden Resultate (erste Primzahl) vergleichen (welche ist näher dran?)
:o das wäre sehr blöd, die nächste primzahl so zu errechnen. die nächste primzahl könnte ja auch über x liegen. außerdem verbrauchst du unnötig rechenzeit und machst alles viel zu kompliziert
und was ist da dann der unterschied zur hashmap ??? oder wird der boolean dazu automatisch generiert ?
Ja das kann sein aber ich will ja eh nur unter x haben, aber du hast recht mit der rechenzeit bei 30k abwärts dauert das schon ein gaaaaanzes stück!
Auf der Wikipedia-Seite des Eratosthenes-Siebes gibt's den Code als Pseudocode, auf dieser Seite sind auch einige Optimierungen erklärt. Den Vorgang, diesen Pseudocode in Java zu übersetzen, bezeichnet man auch als "programmieren", das kann dir keiner abnehmen. Und dann musst du nur noch gucken, welchen Wert deine Zahl im Sieb hat.
du überprüfst einfach um x herum (vielleicht 100 zahlen) ob die momentane zahl eine primzahl ist . dann vergleichst du die ergebnisse auf beiden Seiten
if(x-1 >= 1){ return;
while(isprim == false){ // primzahlprüfung
}
//nachdem die primzahl ermittelt wurde
if(primoberhalb >= primunterhalb){
return primoberhalb; }
else {
return primunterhalb;
}
Servus, Tante Wiki weiß auch das:
http://de.wikibooks.org/wiki/Primzahlen:_Programmbeispiele#Java
Der mann ist gut!
Ich habe nur rotz dazu gefunden -.-
Danke für die Hilfe!! :)
Das Programmbeispiel ist aber auch Rotz... der Primzahltester ist (gerade für große Zahlen) ziemlich ineffizient.
ist mir auch aufgefallen, nach 30k wirds echt ätzend
Oje,
Die Routine braucht nicht bei 1 starten, sondern kann ab einer beliebigen Zahl gestartet werden, sie wird dann effizienter!
Voraussetzung ist das Streichen in einem Array.
https://de.wikipedia.org/wiki/Sieb_des_Eratosthenes
Lege ein 1000er Array an und streiche darin die Zahlen wie Wiki es zeigt!
Ich hab sie schon mal selbst gebraucht, aber frag bitte nicht, wo ich das Ding jetzt habe!
http://de.softuses.com/53528
Vielleicht helfen die Routinen weiter! Es sind neuere Algorithmen!
mein problem ist doch ein ganz anderes,
ich habe eine zahl x und will die nächst kleinere primzahl davon haben wie bewerkstellige ich das in java?
Achtung Virus!!! Seite hat zwar einiges über Prime... aber zig ActiveX , Cookies und Virenseiten im Hintergrund!!! Nur mit Browser ansehen, wo alles abgeschaltet ist!
softuses ist allgemein doof, weil die alles automatisiert auf deutsch übersetzen und man kaum versteht, was die da eigentlich schreiben.
public class Primzahl {
public static void main(String[] args) {
boolean gefunden=false;
int limit = 100000000;
int i;
int zahl; // Zu überprüfende Zahl
int zaehler; // Durch diese Zahl soll geteilt werden
int teiler; // Anzahl der möglichen Teiler
int zahl2; // Rest bei der Division
zahl = limit-1;
do
{
if (zahl == 1) // Ausschluss der Zahl 1 als Primzahl
{
System.out.println("");
} else {
teiler = 0;
for (zaehler = 1; zaehler <= zahl; zaehler++) // Es empfiehlt sich den Terminationswert auf zahl zu
//setzen und nicht auf limit, da die Berechnung von Primzahlen
//bis zu Milliardenbeträgen sonst nur äußerst langsam
//funktioniert. Die Teilung durch Zahlen, die größer sind als
//die zu überprüfende Zahl selbst ist ohne hin obsolet.
{
zahl2 = zahl % zaehler; // Division der Ausgangszahl durch eine weitere und ablegen des Rests in der Variabel zahl2
if (zahl2 == 0) // Falls der Rest gleich 0 ist ist ein Teiler gefunden
{
teiler++;
}
}
if (teiler == 2) // Wenn die Zahl genau 2 Teiler hat ist sie eine Primzahl
{
gefunden=true;
System.out.println(zahl + " ist eine Primzahl, da sie genau " + teiler + " Teiler hat");
}
/*else // Andernfalls ist sie keine Primzahl
System.out.println(zahl+" ist KEINE Primzahl");*/
}
zahl--;
}while (!gefunden);
}
}
So, das Sieb des Erastotenes, du kannst sie als Test nach Suboptimierers tendenziöser Prüfung laufen lassen.
Für den Fall von z+=2 muss man aber überprüfen, ob die Zahl gerade ist und wenn ja, ob es sich um die Zahl 2 handelt.
Ansonsten wird jede gerade Zahl als Primzahl erkannt.