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

Beitragsersteller

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

Beitragsersteller

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.

Ähnliche Beiträge

Natürliche Zahl die durch keine Primzahl teilbar ist?

Gibt es eine natürliche Zahl größer als 1, die durch keine einzige Primzahl teilbar ist? Wenn ja, Begründung?

...zum Beitrag

Rätsel mit Primzahlen als Summe

In ein Quadrat (wie beim Sudoku) mit 3 x 3 Feldern sollen die Zahlen 0,1,2,3,4,5,6,7,8 so eingetragen werden, dass die Zeilensummen, Spaltensummen und Summe der Diagonalen immer Primzahlen ergeben.

Ich sitze nun schon seit längerem über diesem Rätsel und finde keine Lösung. Wäre nett wenn mir jemand helfen könnte.

...zum Beitrag

Kann man jede gerade Zahl größer als 2 als Summe zweier Primzahlen schreiben?

wisst ihr es

...zum Beitrag

Wie berechnet man eigentlich eine Primzahl?

Hey,

muss für eine Programmieraufgabe in C ein Programm schreiben wo der Benutzer eine Primzahl eingibt und das Programm berechnen soll, ob es sich dabei um eine Primzahl handelt. Un da ich nicht wie ein kleiner Lümmel fragen möchte, ob ihr meine Programmier-Hausaufgabe machen könnt, bitte ich einfach nur darum, wie man eine Primzahl berechnet, ich komme einfach nicht dahinter.

Danke im Vorraus.

...zum Beitrag

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.

...zum Beitrag

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

...zum Beitrag

Python: Primzahlen erkennen?

Ich möchet gerne ein Programm schreiben das Primzahlen erkennen kann wie mach ich das?? ich weiß nur das ich mit der Probedivision arbeiten muss und welche Zahlen von 2 bis n-1 mit Rest teilbar sind.

...zum Beitrag

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

...zum Beitrag

Mathe Primzahl Frage?:

Wähle dir zwei verschiedene zweistellige Primzahlen aus. Bilde aus ihnen durch Hintereinanderschreiben die beiden möglichen vierstelligen Zahlen. Wenn du nun die kleinere der beiden vierstelligen Zahlen von der größeren subtrahierst, dann erhältst du deren Differenz.

Warum kann keine der Differenzen eine Primzahl sein???

...zum Beitrag

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

...zum Beitrag

Java-Programm Primzahlen ermitteln geht nicht ganz?

Das Programm soll entweder einen String ausgeben der sagt, dass es eine Primzahl ist (%==0) oder aber den kleinsten Teiler.

Mein Problem: Da das i mehrere Zahlen in der Schleife annimmt gelten in Fällen, wo die Zahl teilbar ist beide Strings ausgegeben.

Jemand eine Idee wie ich das korrigieren könnte?

(Programmiere seit 1 Tag)

...zum Beitrag

Warum lastet Python meine CPU kaum aus?

Ich habe gerade ein Programm in Python mit Hilfe meiner IDE Pycharm geschrieben, welches überprüft, ob eingegebene Zahlen Primzahlen sind. Jetzt wollte ich das ganze mal mit größeren Primzahlen ausprobieren und habe "188748146801" eingeben. Das Programm rechnet jetzt schon eine ganze Weile, wobei im Task Manager anzezeigt wird, dass meine Hardware quasi nicht beansprucht wird. Warum kann auf Kosten von Leistungsaufwand der Prozess nicht schneller ablaufen? Liegt das daran, dass Python nicht gerade die effizienteste Programmiersprache ist oder limitiert Pycharm die Leistung, die beansprucht wird?

Der Code sieht folgendermaßen aus:

input1 = int(input())
prime = True

for num in range(2,input1):
    if input1 % num == 0:
        prime = False
        break

if prime == True:
    print(input1,"is a prime number")

else:
    print(input1,"is not a prime number")

...zum Beitrag

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

...zum Beitrag

Summe berechnen?

Man soll von 2 bis 4294967296 alle Primzahlen addieren. Hat dafür jemand nen passendes Programm und dafür das Ergebnis?
Danke!

...zum Beitrag

Was möchtest Du wissen?

Deinen Beitrag erstellen