Primzahlen - Wann macht ein Computer schlapp?

Wenn der Computer die Aufgabe erhaelt, die hoechste Primzahl

https://www.mathe-lexikon.at/arithmetik/natuerliche-zahlen/teilbarkeit/primzahlen/primzahlen-bis-500.html

auszurechnen, wann gibt er das Signal "Ich kann nicht mehr"?

3 Antworten

17.01.2022, 22:31

Primzahlen bis 500 sind sogar für einen C64 kein Problem.

Halbwegs gut geschriebene Programme können auf einem ganz normalen PC in einer Sekunde mehr als 1000 Primzahlen ausgeben. Allerdings gibt es keine Methoden, die diese Anfangsgeschwindigkeit beibehält, je mehr Primzahlen man gefunden hat, desto langsamer wird das Programm.

Primitive Methoden gehen so vor: Sie klappern alle ungeraden Zahlen nach oben gehend ab und versuchen sie, durch die schon gefundenen Primzahlen zu teilen. Kommt bei keiner dieser Divisionen eine natürliche Zahl heraus, wurde eine Primzahl gefunden. Die wird in die Liste aufgenommen. Das Dumme dabei ist, dass diese Liste immer länger wird und das Überprüfen einer Zahl immer langsamer.

Etwas bessere Programme starten einen zweiten Thread, der die Folge der ungeraden Vielfachen der gefundenen Primzahlen bildet. Diese werden in eine zweite Liste eingetragen. Es ist die Liste der Zahlen, die keine Primzahlen sein können. Multiplikationen sind schneller als Divisionen, das ist der Trick dabei. Eine neue Zahl wird überprüft, indem die Liste abgefragt wird, ob die Zahl darin vorkommt, ist sie nicht in der zweiten Liste, so wird sie in die erste Liste aufgenommen. Wichtig dabei ist, dass die zweite Liste immer ausreichend Vorrat hat, also sämtliche Folgen der ungeraden Vielfachen der gefundenen Primzahlen mindestens so groß sind wie die zu prüfende Zahl. Alle kleineren Zahlen fliegen automatisch raus.

Gringo58

Fragesteller

17.01.2022, 22:53

Sagen wir so: Ein Hochleistungscomputer von Cray oder IBM schafft welche Primzahl ?

Kwalliteht

17.01.2022, 23:03

@Gringo58

Keine Ahnung.
https://www.scinexx.de/news/technik/das-ist-die-groesste-bekannte-primzahl/

Gringo58

Fragesteller

17.01.2022, 23:06

@Kwalliteht

Super. Aber das war 2018. Werden die Computer (Leistung) schneller oder bleiben so, wie bisher ....?

Tannibi

Nutzer, der sehr aktiv auf gutefrage ist

im Thema Mathematik

18.01.2022, 00:40

Mit KI sagt er dir, dass es keine höchste Primzahl gibt, ohne KI rechnet er, solange du willst.

Gringo58

Fragesteller

18.01.2022, 00:43

Macht Sinn !

Gringo58

Fragesteller

18.01.2022, 00:54

Zur Belohnung: Am Forschungszentrum Jülich steht seit heute ein kommerzieller Quantenrechner. Es ist ein Rechner der kanadischen Firma D-Wave mit 5000 Quantenbits. Die leistungsfähige Maschine soll vor allem komplexe Optimierungsaufgaben lösen.... https://www.faz.net/aktuell/wissen/physik-mehr/quantensprung-am-forschungszentrum-juelich-17735287.html

gfntom

Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer

Mathematik

17.01.2022, 22:13

Wenn der Computer die Aufgabe erhaelt, die hoechste Primzahl auszurechnen

Primzahlen rechnet man nicht aus, sondern ermittelt sie.

"der Computer" erhält keine Aufgaben, er arbeitet Algorithmen ab. Das Verhalten ist dabei vom Algorithmus determiniert.

Sprich: wenn richtig programmiert, "gibt" er nie "auf" (theoretisch, wenn ihm der Speicher ausgeht. Das sollte aber heutzutage kein Thema mehr sein)

Gringo58

Fragesteller

17.01.2022, 22:23

Gut. Aber unendlich lang wird er nicht rechnen .....

Kwalliteht

17.01.2022, 22:35

Primzahlen rechnet man nicht aus, sondern ermittelt sie.

Um sie zu ermitteln muss man aber rechnen, also wäre ich jetzt nicht so pingelig mit dem Begriff.

Die Rechenleistung ist hoch. Wird sie noch hoeher?

Oder geht das Momentum sogar eher zureucek ?

Haengt sicher auch mit der Leistungsfaehigkeit der Halbleiter ab ?

Ich komme auf deise Frage, weil:

https://www.gutefrage.net/frage/primzahlen---wann-macht-ein-computer-schlapp#answer-434028382

...zur Frage

Warum wurden die Primzahlen noch nicht gelöst?

Warum gibt es eigentlich noch keine einfache Rechnung für die Primzahlen?
Ich meine es ist eine Zahlenfolge welche immer weiter ansteigt.
Dafür muss es doch eine einfache Rechnung geben. Aber die gibt es nicht.
Woran liegt das?
Und was würde es bedeuten wenn irgendwann jemand das lösen könnte bzw eine Rechnung dafür finden würde?
Sind nicht alle Computer-Sicherheitsysteme auf Primfaktorzerlegung aufgebaut oder sowas?
MfG

...zur Frage

Primzahlen in Python ausgeben?

Hallo, bin Programmier-Anfänger und stelle mich ziemlich doof an. Im Folgenden ist ein Programm, das Primzahlen generiert. Ich verstehe aber nicht was der Computer mach, auch wenn das Programm sehr einfach ist. Kann mir einer an den Primzahlen "2, 3, 5" konkret erklären, was da ausgerechnet wird?

p=2

while True:

  t=2
    
  while p%t !=0 and t<p:
        
     t= t+1
   
  if t==p:
        
     print p

p=p+1

...zur Frage

Große Primzahl als verschlüsselung?

Mal angenommen ich habe einen Quantencomputer der mir eine sehr große Primzahl berechnet die mit normalen Computern nicht auffindbar oder berechenbar ist. Könnte man dann nicht mit dieser Zahl ein PC System als "Unhackbar" (oder auch verschlüsselung) machen da niemand diese verschlüsselung knacken könnte?

...zur Frage

Eine neunstellige Primzahl?

Ich brauche neunstellige Primzahl die aus den Ziffern von 1 bis 9 besteht, wobei jede nur einmal vorkommt.

...zur Frage

Lohnt sich dieser PC für Grafikdesigner? HP Envy 17-ae142ng?

Hallo, Ich arbeite sehr viel mit Photoshop und bald wahrscheinlich auch 3d Programmen und mein alter PC macht schlapp. Aber ich weiß nicht ob sich dieser PC hier für ca. 1800€ lohnt.

https://m.cyberport.de/hp-envy-17-ae142ng-notebook-i7-8550u-uhd-4k-ssd-geforce-mx150-windows-10-1C24-5YT_1695.html

Typisch für Grafikdesigner ist ja Mac aber das liegt preislich für scheinbar gleiche oder weniger Leistung nochmal ordentlich höher.

Mein Vater, der mit Computern arbeitet, meinte es höre sich toll an, da es einen 4k screen, 1TB SSD, 16gb RAM gute Grafikkarte etc hat. Aber der Preis ist schon nicht ohne, weswegen ich eure Meinung mal hören wollte. Lohnt sich das? Könnte ich was besseres kaufen oder billiger mit selber Leistung? Danke schonmal!

...zur Frage

Wann habt ihr euren ersten Computer/Laptop erhalten?

Oder gekauft

...zur Frage

Ab wann sollte ein Kind einen Eigenen Computer haben (+Internet)

...zur Frage

Ab wann ist ein Experte für euch ein Experte?

Reicht wenn er 10 Computer zusammenbauen kann, muss er ein Master-Studium vorweisen, 30 Jahre Berufserfahrung haben oder umfassendes Fachwissen vorweisen können?

Ab wann ist ein Experte ein Experte für euch persönlich? Speziell auf das Thema Computer/Informatik bezogen.

...zur Frage

Unterschiede bei der Entwicklung des PC und Computer?

Welche Unterschiede oder auch sogar Gemeinsamkeiten gab es bei der Entwicklung von PCs und Computern? Wann wurde der PC erfunden? Ab wann galte der Computer als PC?

...zur Frage

C#: Problem mit der Schleife in der Primfaktorzerlegung?

Hallo zusammen,

ich programmiere gerade mit ASP.NET eine Anwendung, die eine Primfaktorzerlegung durchführt. Um ASP:NET-Anwendungen zu erstellen, wird eine .NET-Programmiersprache benötigt. In meinem Fall ist es C#.

Meine Frage:

Bei manchen Zahlen hört die Schleife nicht auf zu rechnen. In meinem Fall ist immer dann, wenn ich die Zahl 2, 4 8, 9, 16, ... eingebe. Bei den anderen Zahlen klappt die Zerlegung.

Es wäre nett, wenn sich jemand die Schleife anschauen und mir sagen könnte, was ich ändern muss.

Danke im Voraus.

Luca

@page
@{
  var zahl = 0;
  int teiler = 1;
  
  if (Request.Method == "POST")
  {
    zahl = Convert.ToInt32(Request.Form["zahl"]);
  }
}
<html>
  <head>
    <meta charset="utf-8" />
    <title>Primfakorzerlegung</title>
  </head>
  <body>
    <div style="font-family: Courier">
      <h1>Primfaktorzerlegung</h1>
      <form  action="" method="POST">
        Zahl: <input name= "zahl">
        <p>
        <br>
        <input type="submit" value="Primfaktorzerlegung">
      </form>

      @if (Request.Method == "POST")
      {
        <nobr>@zahl = </nobr>
      }

      @{ Console.Write(zahl + " = "); }
      @{
        do
        {
          teiler++;

          while (zahl % teiler == 0)
          {
            zahl = zahl / teiler;
            <nobr>@teiler * </nobr>
            Console.Write((teiler) + "*");
          }
        }
        while ((zahl/teiler != 1) && (zahl%teiler != 0));
      }

      @{ Console.WriteLine(zahl); }

      @if (Request.Method == "POST")
      {
        @zahl
      }
  </body>
</html>

...zur Frage

Nanosekunden messen mit Computer

Handelsübliche Prozessoren haben ja eine Taktung von 1 oder mehr Gigahertz (10^9/s). Ist es dann nicht auch möglich mit diesen genau die Zeit im Nanosekunden (10^-9s) Bereich zu messen? Also gibt es einfach die Möglichkeit, dass mir der Rechner auf die Nanosekunde genau die Zeit angibt? Das wäre ja für ein paar Messungen sehr nützlich (wann genau geht wird ein Signal empfangen - Stichwort Laufzeitberechnung), befürchte nur, dass ich dort ein grundlegendes Problem übersehe und das ganze trotz der Prozessorleistung nicht genau genug ist…

Vielen Dank schon mal falls mir da jemand weiterhelfen kann.

...zur Frage

Wann sind zwei Zahlen teilerfremd?

das sind ja Zahl die nur als gemeinsamen Teiler die eins haben. Das sind dann doch einfach die Primzahlen oder nicht?

...zur Frage

Wie kann eine Computer abstürzen?

Wie und wann stürzt der Computer eigentlich genau ab?

...zur Frage

Was möchtest Du wissen?

Deine Frage stellen