Primzahlliste |
| 16.11.2009, 22:47 | SoerenC | Auf diesen Beitrag antworten » |
| Primzahlliste ich brauche eine Liste aller Primzahlen von 1 Ziffer bis 100 Ziffern. Weiß jemand, wo ich die herbekommen kann? Ich habe zwar schon etwas gegoogled, aber die Ergebnisse waren alle unvollständig oder unbefriedigend. Das ist keine Bitte an andere für mich auf die Suche zu gehen, dass kann ich selbst tun. Falls aber jemand etwas helfen möchte, wäre ich dankbar. Es geht um eine Art Wette mit meiner Professorin, die mir 3 Übungsblätter erlässt, wenn ich zu einer bestimmten vorgegebenen Zahl, die einzigen beiden Primfaktoren finde. Die Zahl hat eben 100 Ziffern. Der größte Primfaktor müsste also maximal die Größe der Wurzel dieser Zahl haben. Sie sagt, es sei gar nicht so einfach. (was ich ihr ja glaube. möchte es dennoch gerne versuchen.). Interessante wäre hier auch eine Art Onlinerechenpower, eine Art kleiner "super"computer dessen Rechenzeit ich mir online etwas ausleihen darf.... ja, ich weiß, es klingt größenwahnsinnig. aber so bin ich in diesem fall eben ;-) |
||
| 16.11.2009, 22:52 | MLRS | Auf diesen Beitrag antworten » |
| RE: Brauche Primzahlliste Es gibt einige Programme, die nur darauf spezialisiert sind, große Zahlen zu faktorisieren... ...aber bei 100 Stellen dauert es mindestens 24h Rechenzeit, wahrscheinlich deutlich länger (wenn ich das größenordnngsmäßig noch richtig in Erinnerung hab) Also bereite dich lieber auf die Übungsblätter vor, da können wir helfen 
edit: ich setzte mal voraus, du bekommst eine Zahl, die nur 2 riesige Faktoren hat, ansonsten gehts wohl relativ schnell PS: Herauszufinden, ob die Zahl zusammengesetzt ist oder nicht, dauert wenige Sekunden 
|
||
| 16.11.2009, 22:56 | SoerenC | Auf diesen Beitrag antworten » |
| RE: Brauche Primzahlliste Wie meinst Du das? Wenn es nur wenige Sekunden dauert, dann geht das ja nur, wenn man auch weiß, woraus. Oder, verstehe ich falsch? |
||
| 16.11.2009, 22:58 | DGU | Auf diesen Beitrag antworten » |
Nein, es gibt Algorithmen, die sehr effizient herausfinden, ob eine Zahl prim ist oder nicht, im Falle der Zusammengesetztheit aber keine Faktoren liefern. |
||
| 16.11.2009, 23:00 | kiste | Auf diesen Beitrag antworten » |
Ich hab es nur grob abgeschätzt: Aber in der Zeit die du brauchst allein zum Faktorisieren sollten alle 3 Übungsblätter schon längst abgegeben sein müssen! An eine Tabelle aller Primzahlen bis dahin ist erst gar nicht zu denken 
|
||
| 17.11.2009, 07:29 | Mystic | Auf diesen Beitrag antworten » |
Statt um den heißen Brei herumzureden, würde es mehr bringen, die Zahl, um die es hier geht, einfach einmal zu posten... |
||
| Anzeige | ||
|
|
||
| 17.11.2009, 19:50 | SoerenC | Auf diesen Beitrag antworten » |
Ich würde es nicht um den heißen Brei reden nennen, sondern Faulheit zum fehlerfreien abtippen. Sobal ich wieder hinter einem PC mit Nummernblock sitze, tippe ich die Zahl ab. Wer siich dran probieren möchte, kann das dann gerne tun. |
||
| 25.08.2010, 16:31 | SuiCid | Auf diesen Beitrag antworten » |
Auch wenn schon alt: Wie du ja schon sagtest, brauchst du nur bis zur Wurzel testen... mit Anzahl der Primzahlen von 1 ... x =x/ln(x) kommt man auf 8,6858896380650365530225783783321e+47 Zahlen runden wir auf 88*10^46 bei einem Bit pro Zahl (ich schaffe fast immer ein Byte pro Zahl und das ist schon gar nicht schlecht) sind das also noch 11*10^46 Bytes wir rechnen mal mit 1kb = 1000 Bytes, man kann leichter teilen und wenn man es auf Platte speichern will, dann wird man heute ja eh auf genau diese Weise beschissen... Kilo, Mega, Giga, Tera,... ist ja gängige Größe - sagen wir 2 TB pro Platte... 5,5*10^34 Platten voll mit Daten (könnte sich nicht mal Bill Gates mit nem großen Mengenrabatt leisten) oder einfach 11*10^34 TB an Daten bei 1PB/s (= 1024 TB/s) würdest du wohl länger brauchen als dem Universum bleibt, auf jeden Fall könnte frühestens dein Urururururururururururururururur...........enkel zu deiner Professorin gehen um deine Urkunde für den Abschluss zu erhalten... sagen wir mal, dass wir dir die Daten auf 1TB-Platten schicken... jede Platte hat nur 1g und 1cm³, die Daten sind schon drauf und die Post ist mal schnell (Zeit ist egal)... 11*10^31 Kilo ~= 2,2*10^28 (schwere) Elefanten bzw. mehr als 10^9 Versionen unseres Mondes - mal auf der Zunge zergehen lassen... 1 Mrd. Monde! das Volumen wäre dritte Wurzel aus (11*10^29) = dritte Wurzel aus (11*10^2) *10^9 ~= dritte Wurzel aus (10^3) *10^9 = 10^10 10 Mrd. km³ (hoffe ich hab mich nicht verrechnet 
das wäre immerhin ein halber Mond...also, wir sollen wir die Daten durch die Zeitmaschine schicken?
MfG Cid |
||
| 25.08.2010, 18:02 | SuiCid | Auf diesen Beitrag antworten » |
PS: Wenn du deine 8,6858896380650365530225783783321e+47 Zahlen alle durchtestest auf 1.000.000.000 Clustern mit 1.000.000.000 Rechnern, die jeweils (durch Nutzung von 10x-GPU-Power, mehrere Multikern-CPUs, Stickstoffkühlung,.... oder was weiß ich wie) 1.000.000.000.000 Zahlen pro Sekunde* schaffen, sind das bei nem positiv denkenden Menschen, der an Glück im Lotto glaubt (1:140 Millionen) immer noch 196 JAHRE! *was ein Witz ist, wenn man bedenkt, dass man mit ~332 Bit Zahlen = 41,5 Byte = 10,375 ulong (4 Byte) >= 5 ulong long (also 5 64 Bit-Register) rechnen muss Vergleiche sind im Schnitt sublinear wachsend (lasse ich hier mal raus) Subtraktionen / Additionen wachsen linear = O(n) --> (mindestens) 5 * teurer als rechnen mit 64 Bit Zahlen Multiplikationen / Modulo wachsen quadratisch = O(n²) --> (mindestens) 25 * teurer als rechnen mit 64 Bit Zahlen dazu dann noch, dass man mit nem Viererverbund (gibt es) aus 5 GHz Quadcore (wird es wohl nie geben) nicht 1000 Mrd. Zahlen die Sekunde schafft, sondern nur 80 Mrd. maximal... dass du nicht 1 Mrd. Cluster mit je 1 Mrd. Rechenknechten kriegen wirst, muss ich ja wohl nicht noch erklären... vielleicht kannst du ja mit nem (größeren) Quantencomputer das Problem leicht beschleunigen?!? |
||
|
|