primzahlensieb
-
hallo
ich möchte den bereich x..y nach primzahlen durchsuchen mit dem sieb des eratosthenes. meine ideen:
1. den bereich 2..sqrt(y) sieben und die primzahlen davon dann über den bereich x..y faktorisieren.
2. den bereich sqrt(x)..sqrt(y) sieben mit der selben mehthode wie hier geschrieben (das ganze funktioniert dann rekursiv) und dann die primzahlen davon über x..y faktorisieren.mit "primzahlen über x..y faktorisieren" meine ich dass ich die vielfache (x/p..y/p) der primzahlen im sieb mit dem bereich x..y gestrichen werden.
kommt man mit beiden varianten an eine korrekte lösung? gibt es dazu effizientere vorgehensweisen die mir nicht eingefallen sind?
gruss
-
Welche Größenordnung haben x und y ungefähr? Eher 10^10 oder eher 10^1000?
-
SeppJ schrieb:
Welche Größenordnung haben x und y ungefähr? Eher 10^10 oder eher 10^1000?
es geht mir eher darum zu wissen wie das prinzipiell geht und welcher ansatz welche vor- / nachteile hat, rein aus neugier und interesse also.
-
asfdlol schrieb:
SeppJ schrieb:
Welche Größenordnung haben x und y ungefähr? Eher 10^10 oder eher 10^1000?
es geht mir eher darum zu wissen wie das prinzipiell geht und welcher ansatz welche vor- / nachteile hat, rein aus neugier und interesse also.
Wenn du in einer Größenordnung bist, wo Sieben in vernünftiger Zeit läuft, dann siebe! Das ist eine superschnelle Methode um alle Primzahlen bis Y und damit auch alle Primzahlen von X bis Y zu finden. Da das dann insgesamt eine schöne übersichtliche Liste ergibt, kannst du das sogar einmal laufen lassen und das Ergebnis speichern. Primzahlen sind schließlich konstant, die muss man nicht bei jedem Programmlauf neu berechnen.
Wenn wir aber von wirklich großen Zahlen reden, etwa alle Primzahlen zwischen 4646464613791374731381371871431771713774173171713161437139137137841313733716443171636717 ... tausend Stellen ... 13431380000
und
4646464613791374731381371871431771713774173171713161437139137137841313733716443171636717 ... tausend Stellen ... 13431381000, dann kommst du mit dem Sieb nicht weit. Da muss dann eben ein Primzahltest auf jede einzelne Zahl her. Die sind zwar sehr aufwändig (besonders die deterministischen, die probabilistischen gehen sogar), aber noch machbar - im Gegensatz zum Sieb.
-
hallo. ich hab eigentlich auf etwas mehr rückmeldung gehofft, deswegen hab ich solange nicht geantwortet.
SeppJ schrieb:
Wenn du in einer Größenordnung bist, wo Sieben in vernünftiger Zeit läuft, dann siebe! Das ist eine superschnelle Methode um alle Primzahlen bis Y und damit auch alle Primzahlen von X bis Y zu finden. Da das dann insgesamt eine schöne übersichtliche Liste ergibt, kannst du das sogar einmal laufen lassen und das Ergebnis speichern. Primzahlen sind schließlich konstant, die muss man nicht bei jedem Programmlauf neu berechnen.
joa, das ist mir bewusst.
SeppJ schrieb:
Wenn wir aber von wirklich großen Zahlen reden, etwa alle Primzahlen zwischen 4646464613791374731381371871431771713774173171713161437139137137841313733716443171636717 ... tausend Stellen ... 13431380000
und
4646464613791374731381371871431771713774173171713161437139137137841313733716443171636717 ... tausend Stellen ... 13431381000, dann kommst du mit dem Sieb nicht weit. Da muss dann eben ein Primzahltest auf jede einzelne Zahl her. Die sind zwar sehr aufwändig (besonders die deterministischen, die probabilistischen gehen sogar), aber noch machbar - im Gegensatz zum Sieb.ja, genau sowas wollte ich machen.
ich hab ein wenig an meinen beiden ideen rumprobiert (nur auf papier bisher) und hab gesehen, 1. stimmt, 2. leider nicht.
aber da die erste idee stimmt kann ich z.b. den bereich 1010..1015 blitzschnell sieben weil ich dazu nur 0..sqrt(10^15) (=0..3.2*10^7) sieben muss (was ja sogut wie sofort geht) und dann über den bereich faktorisieren kann. beim bereich von 1000 dezimalstellen geht das leider nicht mehr so toll weil ich da damit immer noch von 0..10^500 sieben müsste bevor ich faktorisieren kann (das wollte ich eigentlich mit der zweiten idee verhindern). schade eigentlich.danke dir für die hilfe.
-
Du hast soeben den Grund gefunden, wieso nicht alle Primzahlen zwischen 1*10^1000 und 2*10^1000 bekannt sind
-
Normalerweise wird ein Primzahlrad (prime wheel) benutzt, um sowohl Rechenaufwand und Platzbedarf drastisch zu verringern. Schnellstes mir bekannte Programm ist: http://primesieve.org/ . Versuch dich aber erstmal mit normalen Prime wheels und nicht mit der Cache-optimierten Variante. Ein einfaches Beispiel ist fuer ein segmentbasiertes Sieb gegeben.
-
knivil schrieb:
Normalerweise wird ein Primzahlrad (prime wheel) benutzt, um sowohl Rechenaufwand und Platzbedarf drastisch zu verringern. Schnellstes mir bekannte Programm ist: http://primesieve.org/ . Versuch dich aber erstmal mit normalen Prime wheels und nicht mit der Cache-optimierten Variante. Ein einfaches Beispiel ist fuer ein segmentbasiertes Sieb gegeben.
danke für das stichwort, werde ich mir demnächst mal anschauen.