Primzahlen ermitteln aus dem Produkt zweier Primzahlen?

Hallo zusammen,

ich bin auf der Suche nach einer Lösungsmöglichkeit für folgendes Rätsel:

Ich habe die Zahl 373136061186515427613

Diese ist selbst keine Primzahl sondern das Produkt aus den Primzahlen A und B, wobei A die größere der beiden Primzahlen ist.

Nun meine Frage gibt es ein Programm welches die Primzahlen aus dem oben genannten Produkt wieder berechnen kann?

Danke schonmal für eure Antworten.

Alex

2 Antworten

Vom Fragesteller als hilfreich ausgezeichnet

ultrarunner

21.04.2020, 17:09

Das tut eigentlich jedes Primzahltestprogramm.

Es dividiert die Ausgangszahl so lange durch Primzahlen, bis es eine findet, bei der es sich ohne Rest ausgeht. Dann hat es den ersten Primfaktor gefunden.

Wenn man schon weiß, dass die Zahl nur zwei Primfaktoren hat, hat man damit den zweiten auch schon bestimmt.

AlexST76

Fragesteller

21.04.2020, 17:40

Hallo ultrarunner,

danke schoneinmal für Deine Antwort. Kennst Du ein bestimmtest Programm welches sich mit der langen Zahl (21-stellig) auseinandersetzen kann? Die meisten, welche ich bsiher gefunden haben hören spätens nach 20 Stellen auf.

ultrarunner

21.04.2020, 20:05

@AlexST76

Dieses hier ist zwar voll mit Werbung, kann deine Zahl aber faktorisieren:

https://www.dcode.fr/prime-factors-decomposition

373136061186515427613 = 14797203313 × 25216661101

ultrarunner

21.04.2020, 20:08

@ultrarunner

Ach ja, Wolfram Alpha kann es auch:

https://www.wolframalpha.com/input/?i=factor+373136061186515427613

AlexST76

Fragesteller

21.04.2020, 21:03

@ultrarunner

Hallo ultrarunner,

vielen Dank für Deine Mühe. Ich habe das ganze jetzt mal bei wolframalpha eingegeben mal sehen wie lange es bis zu einem Ergebnis dauert.

Waldmensch70

21.04.2020, 17:08

Siehe hier: https://de.wikipedia.org/wiki/Primfaktorzerlegung

Wenn Du das schaffst, dann hast Du mal eben das weltweit im Internet im Einsatz befindliche RSA Verschlüsselungsverfahren ausgehebelt, weil das darauf basiert dass es eben kein effizientes Verfahren zur Zerlegung einer Zahl in ihre Primfaktoren gibt.

Z.B. 41 ist eine Primzahl. Deren Quadrat ist 1681

1681 lässt sich aber nur durch 41 teilen. Da klappt es also nicht.

Was also ist die kleinste Quadratzahl einer Primzahl, die sich auch anders zerlegen lässt?

...zur Frage

Was jemand was mit diesem Abschnitt in der papula formelsammlung gemeint ist?

Also zum Beispiel 2mal 70.

Da steht Produkt aus Primzahlen. OK 2 ist eine Primzahl aber doch nicht die 70,weil die nicht nur durch sich selbst und durch 1 Teilbar ist sondern auch durch 2 oder auch 35 ect.

Klärt mich mal bitte auf was jetzt daran ein Produkt dieser Primzahlen sein soll

...zur Frage

Ist jede gerade Zahl Summe zweier Primzahlen?

Mein Vorschlag wäre ein LGS mit

10 = 12Y + 8X

14 = 16Y + 20X

Wodurch hier die Summe zweier geraden Zahlen durch gerade Zahlen gebildet wird, die nicht Primzahlen sind.

Ich erhalte auch für X = 11/14 und Y = 1/14

Wodurch doch bewiesen wäre, dass es zumindest zwei gerade Zahlen gibt, die nicht durch die Summe zweier Primzahlen gebildet werden.

Hab mich sicherlich irgendwo getäuscht. Der "Beweis" ist ja auch zu simpel. Deswegen meine Frage: Wie kann man das Beweisen?

...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

Java - Primzahlen ermitteln

Soll zwischen 1 und 100 alle Primzahlen in Java ermitteln. Lasse ich das Programm laufen wird keine Zahl ausgegeben. Ich habe festgestellt, dass bei jeder Zahl primzahl == false ist. Zu beginn war der boolean primzahl true. Was habe ich falsch gemacht?

System.out.println ("Primzahlen:");

for (i=1 ;i<=100 ;i++ ) {
  if (i==1) {
    primzahl = false;
  } // end of if
    else {
    for (j=2 ;j<i ;j++ ) {
      if (i % j == 0) {
        primzahl = false;
      } // end of if
    } // end of for
  } // end of if-else
  if (primzahl == true) {
    System.out.println (i);
  } // end of if
} // end of for

...zur Frage

Große Primzahlen leicht erkennen?

Hallo,

ich habe eine Aufgabe wo ich die Primfaktorzerlegung bei 116.338.867.864.982.351 anwenden soll. Nun ich habe mir zunächst die Quersumme angeschaut, die ist aber 89 und somit eine Primzahl. Da stellt sich mir die Frage, kann eine Zahl keine Primzahl sein aber trotzdem als Quersumme eine Primzahl haben? Und wenn ja, wie beweise ich das?

Oder ist diese Theorie falsch, und wie gehe ich dann die Aufgabe an?

Ich freue mich über jeden Hinweis,

liebe Grüße

...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

c# Primzahlen?

Hey liebe Community,

ich hätte da mal eine Frage. Ich habe die Möglichkeit, meinen Code etwas zu verändern. Bisher habe ich mit dem Code geprüft, ob die Eingabe des Benutzers eine Primzahl ist. Wie könnte ich es machen, dass z.B. der Benutzer eine Zahl eingibt (4) und die ersten vier Primzahlen ausgegeben werden?

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;

namespace Primzahlen
{
  class Program
  {
    static bool Primzahl(int primzahl)
    {
      bool ergebnis = false;
      int zähler = 0;

      for (int i = 1; i <= primzahl; ++i) // Zahl wird durch Teiler geteilt
      {
        if (primzahl % i == 0) //Teilung ohne Restwert, dann für 1 zum Zähler hinzufügen
        {
          zähler = ++zähler;
        }
      }

      if (zähler == 2) //Wenn Zahl nur durch sich und 1 teilbar ist, Ausgabe (Da Zähler auf 2 ist)
      {
        ergebnis = true;
      }

      return ergebnis;
    }

    static void Main(string[] args)
    {
      Console.Title = "Primzahlen";
      StreamWriter sw = new StreamWriter("Primzahlen.txt");

      Console.WriteLine("Geben Sie eine Zahl ein");
      string eingabe = Console.ReadLine();
      sw.WriteLine(eingabe);
      sw.Close();

      String dateiName = "Primzahlen.txt";
      StreamReader reader = null;
      int zahl = 0;
    
      try
      {
        reader = new StreamReader(dateiName);
        string zeile = reader.ReadLine();
        zahl = Convert.ToInt32(zeile);
      }
      catch (Exception ex)
      {
        Console.WriteLine(ex.Message);
      }
      finally
      {
        if (reader != null)
          reader.Close();
      }

      if (Primzahl(zahl))
      {
        Console.WriteLine("Das ist eine Primzahl");
      }
      else
      {
        Console.WriteLine("Keine Primzahl");
      }

      Console.ReadLine();
    }
  }
}

Vielen Dank!

...zur Frage

Java Primzahlen bis 8 testen?

In Java. Ich möchte alle Zahlen bis 8 testen lassen ob Sie Primzahlen sind oder nicht

Per Scanner wird die 8 eingelesen:

Am Ende soll ausgegeben werden:

Zahl 1 ist keine Primzahl

Zahl 2 ist Primzahl

Zahl 3 ist keine Primzahl

...

Zahl 8 ist keine Primzahl

Wie kriegt man dies hin: Doppelte for-Schleife?

...zur Frage

Frage bezüglich Primzahlen! MATHE! Hilfe!

Hey,

ich hab eine Frage bezüglich Primzahlen. Also Hausaufgaben die ich einfach nicht schaffe. Die Aufgabe lautet: "Denke dir eine beliebige dreistellige Zahl (z.B. 547). Schreibe sie zweimal hintereinander. So ensteht eine sechsstellige Zahl (547547). Warum kannst Du so niemals eine Primzahl erzeugen? Begründe!"

Danke!!

...zur Frage

Excel Formelbefehle: Ist Zahl Primzahl

Hallo,

Ich kenne mich den Formelbefehlen für Excel nicht sonderlich aus und habe eine Frage dazu:

Ich habe in Spalte 1 "Primzahl" eine Liste aller Primzahlen (aus dem Internet kopiert). In Spalte 2 "Zahl" notiere ich mir bis zu einem bestimmten Punkt alle natürlichen Zahlen (1, 2, 3, 4...100). In Spalte 3 "Ist Primzahl" möchte ich jeweils eine binäre Aussage, einen Boolean, von mir aus 1 oder 0, ob die Zahl eine Primzahl ist.

Ich glaube, irgendwann einmal so einen "Suchen"-Befehl gehört zu haben, kann mich aber leider nicht mehr daran erinnern.

Wie geht das?

Mit freundlichen Grüßen,
KnorxThieus

...zur Frage

Java: Primzahlen Programm?

Hallo,

ich muss ein Programm schreiben ob die Zahl n eine Primzahl ist oder nicht. Wenn sie keine ist soll per System.out.println() ausgegeben werden, dass es keine ist. Wenn es eine ist, dann soll sie als Primzahl ausgegeben werden.

...zur Frage

Java Primzahlen Programm

Hey Leute, ich habe mal wieder eine Java-Aufgabe, bei welcher ich den Fehler nicht finde. Ich hoffe ihr könnt mir irgendwie weiterhelfen.

public class PrimeNumbers {

static int x = 1000;
private static boolean[] Primes = new boolean[x];

// Hier ist der "statische Konstruktor"
static {
}

private static boolean checkPrime(int number) {

    return false;
}

public static boolean isPrime(int number) {
    int limit=1000;
    int zahl;      
    int zaehler;   
    boolean primzahl; 

    for (zahl = 2; zahl <= limit; zahl++) {
        primzahl = true;

        for (zaehler = 2; zaehler <= zahl/2; zaehler++) {
            if (zahl % zaehler == 0) {
                primzahl = false;
              break;
            }

        }

        if (primzahl) {
            return true;
        }
    }
    return false;
}

Die Primzahlen, welche zu überprüfen sind werden in einer anderen Methode übergeben und abefragt. Ich habe hier das Problem, dass er mir entweder immer true oder immer false returned, egal ob es nun eine Primzahl ist oder nicht. Ich komme einfach nicht weiter, egal wie ich es drehe und wende. Ich hoffe ihr könnt mir weiterhelfen.

Grüße Dubsepp

...zur Frage

Primfaktorzerlegung bei 151 Stelligem Produkt aus 2 Primzahlen

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

Was möchtest Du wissen?

Deine Frage stellen