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

MagicalGrill

03.12.2020, 12:54

Was ist denn die Quersumme von 14?

Darktheus

Fragesteller

03.12.2020, 12:55

Ah Denkfehler, aber wie komme ich auf die Primfaktorzerlegung von so einer hohen Zahl wenn die Quersumme eine Primzahl ist.

1 Antwort

MagicalGrill

Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer

Mathematik

03.12.2020, 13:05

Nochmal als Antwort:

Ja, eine zusammengesetzte Zahl kann durchaus eine Primzahl als Quersumme haben (siehe 14, 16, 21, ...)

Zur Frage "wie zerlege ich eine große Zahl in Primfaktoren?":

Im wesentlichen durch ausprobieren... Es ist kein effizienter Algorithmus zur Berechnung der Primfaktorzerlegung bekannt, der ohne Quantencomputer auskommt. Wenn du mich fragst, solltest du einfach einen bekannten (und somit langsamen) Algorithmus verwenden, um die Zahl zu zerlegen - so einer lässt sich relativ leicht googeln.

Dein Ergebnis kannst du auch mit dem eines online-rechners vergleichen, z.B. mit diesem hier.

Darktheus

Fragesteller

03.12.2020, 13:10

Und welchen Algorithmus sollte ich dafür benutzen?

Darktheus

Fragesteller

03.12.2020, 13:13

Eventuell mit der Probedivison?

Guten Morgen,

ich wollte mal nachfragen, ob folgende Theorie stimmt: Wenn die Quersumme einer Zahl x nur durch sich selbst und 1 teilbar ist, ist auch die Zahl x eine Primzahl.

Freue mich über hilfreiche Antworten! :)

Grüße

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

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

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

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

Primzahl bestimmen

Woher kann ich herrausfinden, ob eine Zahl eine Primzahl ist?

Sicher, die Zahl ist nur durch sich selbst und 1 teilbar, aber ich kann z.b nicht 236751 durch alle möglichen Zahlen teilen. Ich kannte mal einen Trick mit der Quersumme bin mir da aber nicht mehr sicher. Währe über Hilfe sehr erfreut.

Danke

...zur Frage

SAP ABAP Editor Primzahlen "Generator"?

Ich W(18) muss einen Primzahl Generator erstellen über ABAP (SAP) und ich weiß nicht einmal wie ich anfangen soll. Hab momentan ziemlich Schwierigkeiten mich zu konzentrieren aus irgendeinem Grund. Also in der Aufgabe steht:,, Erstelle ein Programm, welches alle Primzahlen von 1 bis zu einer vom Benutzer vorgegebenen Grenze auflistet. Die Aufgabe soll so aussehen:

Alle Primzahlen von 1 bis 99:

2, 3, 5, 7, 11, 13, 17, 19, 23, .. 89, 97.

Weiß einer wie das funktioniert? Man muss das mit Schleifen machen.. Und evtl nicht so kompliziert machen.

...zur Frage

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"?

...zur Frage

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

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

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

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

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

Was möchtest Du wissen?

Deine Frage stellen