Herausfinden, ob es sich um eine Primzahl handelt (große Zahlen)?

Wie kann man bei großen Zahlen (beispielsweise 4.000 stellig) herausfinden, ob es sich um eine Primzahl handelt?

3 Antworten

11.02.2016, 16:52

Ich glaub, da werden einfach alle Zahlen von einem Computer durchgerechnet. Wenn es dann bis zur Wurzel aus der Zahl keine Zahl gab, durch die sie ganzzahlig teilbar ist, ist es eine Primzahl. Bei den meisten Zahlen kann man ganz schnell berechnen, dass es keine Primzahl ist und beim durchrechnen der Zahlen reicht es auch, wenn man nur prüft, ob die Zahl durch eine andere Primzahl teilbar ist. Wenn eine Zahl z.B. nicht durch eine 2 teilbar ist, ist sie auch nicht durch eine 4, 6, 8 etc. teilbar.

Epicmetalfan

11.02.2016, 17:26

naja die wurzel einer 4000stelligen zahl ist immernoch 2000 stellig. selbst wenn du davon ausgehst, dass ein computer pro sekunde 10^9 zahlen prüfen kann, bräuchte er demnach 10^1991 sekunden um alle zahlen zu testen. zum vergleich, unser universum ist ca 4*10^17 sekunden alt

der computer bräuchte also buchstäblich ewig.

klar musst du an sich nur die primzahlen testen, wie du schon sagtest, aber selbst damit würde er noch ewig brauchen.

diese methode funktioniert einfach nur bei kleinen zahlen

Schachpapa

Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer

Mathematik

11.02.2016, 16:57

Da gibt es spezielle Verfahren https://de.wikipedia.org/wiki/Primzahltest

Der Nachweis, dass eine Zahl prim ist, ist bedeutend einfacher als die Zerlegung einer nicht primen Zahl in ihre Faktoren. Letzteres ist bei einer beliebigen 4000 stelligen Zahl mit heutigen Methoden nicht möglich (prinzipiell schon dauert aber "ewig").

googleFTW

11.02.2016, 16:47

Ein schönes video dazu

https://youtu.be/lEvXcTYqtKU

Der kanal ist nur zu empfehlen :d ist allerdings auf englisch.

lisabckr

Fragesteller

11.02.2016, 16:49

Vielen Dank! Englisch ist für mich gar kein Problem

googleFTW

11.02.2016, 16:55

dann wird dir der kanal gefallen :D falls du die videos durchsuchtest und nachschub brauchst: die besten videos macht james grime. der hat einen eigenen kanal namens singingbanana

Hallo erstmal :) In Informatik gab uns unser Lehrer seinen "RSA Public key", den man braucht um Nachrichten zu kodieren. Diese Zahl ist 151 Dezimalstellen lang und ist das Produkt von 2 Primzahlen. Die Aufgabe ist jetzt diese Beiden Primzahlen, welche die Faktoren der 151 stelligen Zahl sind herauszufinden. Hat jemand eine Idee, wie man das anstellen könnte, oder wie viele Bit die Verschlüsselung stark ist? Danke im Voraus! :) P,S; die Zahl lautet: 19149104522157777914518142786658323647594273709216144656238580509691987587413882641662966440441691453

...zur Frage

c# prüfen ob Primzahl?

Ich soll in C# überprüfen, ob eine Zahl eine Primzahl ist.

So ist der Code in meinem Programm, der das prüfen soll:

  if (zahl/zahl ==1 &&zahl/1 == zahl)
  {
    Console.WriteLine("Es handelt sich um eine Primzahl.");
  }
else
  {
    Console.WriteLine("Es handelt sich um keine Primzahl.");
  }

Ich möchte ihn aber so abändern, das die Zahl eine Primzahl ist, wenn nur die Bedingung gilt und nichts anderes, denn sonst wäre ja alles eine Primzahl.

Danke im Voraus.

...zur Frage

Wie kann ich bestimmen ob eine Zahl eine Primzahl ist?

Hey!

Wie kann ich herausfinden ob eine zahl eine Primzahl ist?

Wir sollen zahlen wie 465.906.763 bestimmen!

bis eine Trilliarde!

Wäre nett wenn ihr helfen könntet.

Unser Lehrer sagt wir sollen das selbst herausfinden,ich chek es aber nicht und wir shen ihn erst am Donnerstag un da schreiben wir auch die Arbeit.

...zur Frage

Welche 7 Stelligen Primzahlen gibt es?

Ist eigentlich selbsterklärend, danke an alle die mir antworten.

...zur Frage

Formel zur Berechnung von Primzahlen?

Gibt es eine Gleichung mit der man aussagen kann, das eine Zahl eine Primzahl ist, bzw. wenn die Gleichung korrekt ist, ist die Zahl X eine Primzahl, wenn sie ungleich ist, handelt es sich um keine Primzahl.

p = Primzahl

k = eine beliebige natürliche Zahl >0

Ich stelle mir das so vor:

X = p = (Wenn das hier mit X übereinstimmt)

oder ähnlich

Oder sind folgende Aussagen bewiesen?

4k+1 = p;

4k+3 = p

Ich würde mich sehr über eine Antwort mit einer Lösung freuen.

MfG André

...zur Frage

11 Stellige Primzahl entdeckt - Etwas besonderes?

Iwi hatte ich sehr viel Langeweile haha und hab nachdem unser Informatik Lehrer mal darüber gesprochen hat ne 11 Stellige Primzahl gefunden. Ist das Iwas tolles/besonderes? .-.
Wenn überhaupt, was sollte ich dann tun?? Oder es einfach für mich behalten?? xD
Aber Vllt würde es der Mathematik und Wissenschaft und bla bla bla helfen.

Und falls das nichts besonderes ist, dann bitte einfach sagen. Aber die höchste Primzahl die ich bis jz im Internet gefunden hab ist gerade mal 7 stellig und ich habe echt viel gesucht.

Also ist es was besonderes?
Und falls ja, was soll ich tun?

...zur Frage

Primzahlen bis 30 ohne dividieren herausfinden?

Das muss ich unbedingt herausfinden. Habe auch nach langem Suchen keinen Lösungsansatz gefunden.

...zur Frage

Wie weiss man, dass das eine Primzahl ist? :O

Gueten Abend,

Ich habe morgen einen Test über Primzahlen. Wie kann ich herausfinden, dass das eine Primzahl ist und dass das keine ist?

...zur Frage

Warum ist 30031 keine Primzahl?

Eigentlich ist doch jede Zahl, für welche folgendes gilt, eine Primzahl: M=p1*p2*...pn+1 (p steht für Primzahl). Dies folgt meines Erachtens nach aus dem Satz von Euklid. Die Zahl M ist entweder eine Primzahl oder eben keine. Wenn es keine ist, muss es durch wenigstens einen Primfaktor teilbar sein, dies aber wegen der 1.

Dieses Muster geht bis zu 2*3*5*7*11+1 auch auf, aber bei 2*3*5*7*11*13+1 nicht mehr. 2*3*5*7*11*13+1= 30031. Wenn ich die Zahl 30031 in so einen Primzahlen-Test eingebe, kommt da raus, dass es sich dabei um keine Primzahl handelt, weil sie irgendwie noch die 59 und was anderes als Teiler hat.

Wie kann das sein?

...zur Frage

Java Unterprogramm Primzahl?

Hallo zusammen,

kann mir jemand dabei helfen, ein Java Unterprogramm zur Berechnung der Primzahl zu entwickeln ? Die Fragestellung lautet wie folgt:

a) Der Benutzer kann eine Zahl x > 1 eingeben. Ist die Zahl größer als 1 wird ausgeben, ob es sich bei der Zahl um eine Primzahl handelt oder nicht. Eine Zahl x ist KEINE Primzahl, wenn eine Zahl zwischen 2 und x–1 existiert durch die sich x ohne Rest teilen lässt. Je nachdem, ob x eine Primzahl ist wird genau folgender Text ausgegeben (x ist durch die eingegebene Zahl zu ersetzen):  x ist eine Primzahl  x ist keine Primzahl

In dem Programm sollen geschachtelte Schleifen benutzt werden.

...zur Frage

Mathe Vera?

Christian erklärt seine Regel mit der Primzahlen finden möchte: "ich verdopple eine Primzahl dann nehme ich diese verdoppelte Primzahl und addiere einmal eins und einmal subtrahiere ich einst so heiß ich zwei Zahlen von den mindestens einer dieser Zahlen eine Primzahl ist" stimmt Christiansregel?

...zur Frage

Primzahlen berechnen in Java?

Hallo,

ich versuche derzeit ein Programm zu schreiben, das mir Primzahlen errechnet. Es lässt sich auch fehlerfrei kompilieren, aber Primzahlen kommen keine raus. Anscheinend wird das Ergebnis automatisch abgerundet. Ich wäre sehr froh, wenn ihr mir den Fehler (oder die Fehler :-) ) aufzeigen könntet oder mir eine bessere Methode schreiben würdet.

public class Primzahlen {
 public static void main (String[] args) {
  int Zahl = 13;
  double d1;

  for(int i = 2; i < Zahl; i++) {
   d1 = Zahl/i;
   int i1 = (int) d1;
   System.out.println(d1-i1 + "  Ergebnis " + Zahl+ "/" + i + ": " + d1 + "  Zahl: " + Zahl + "  Divisor:  " + i);

   if ((d1 - i1) == 0.0) {
    System.out.println(Zahl + " ist keine Primzahl, sie ist durch " + i + " teilbar.");
    break;
   } else {
    if ((i+1) == Zahl) {
     System.out.println(Zahl + " ist eine Primzahl");
     break;
    }
   }
  }
 }
}

Kompilierte Version und Quellcode: http://db.tt/nRNKnOQ2

...zur Frage

Wie kann ich herausfinden, ob es eine Primzahl ist?

Hallo!

Ich habe gerade Schlag den Raaab (mit drei 'a' weil 'Rab' mit zwei 'a' nicht verwendet werden darf) geschaut, da war die Frage ob die Zahl 91 eine Primzahl ist. Aus dem Bauch heruas habe ich nein geraten, und lag recht.

Aber wie kann ich heraus finden ob eine Zahl eine Primzahl, oder keine ist? Da gibts doch ganz einfache Regeln mit der Quersumme usw.

Danke!

...zur Frage

Schriftliche Division mit beispielsweise 4-stelligen Zahlen?

Wenn ich zum Beispiel 4651:3196 im Kopf, also ohne Taschenrechner, rechnen will, wie gehe ich da vor? Ich weiß, bei der Aufgabe kommt irgendwas mit Komma raus, aber ich rede vom Allgemeinen wenn beide Zahlen gleich groß (also Tausender in dem Fall) sind..

...zur Frage

Was möchtest Du wissen?

Deine Frage stellen