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é

10 Antworten

notizhelge

Nutzer, der sehr aktiv auf gutefrage ist

im Thema Mathematik

16.01.2013, 22:22

Formel zur Berechnung von Primzahlen?

So eine Formel gibt es nicht. Es gibt Algorithmen, mit denen man Primzahlen finden kann, aber keine Formel.

4k+1 = p

4·2 + 1 = 9, keine Primzahl.

4k+3 = p

4·3 + 3 = 15, keine Primzahl.

hypergerd

17.01.2013, 17:48

So eine Formel gibt es nicht

doch, siehe unten.
Diese Summenformel ist sogar endlich und nicht unendlich wie die Formeln für sin(x), log(x) usw. (habe sie auch getestet)

Kleinalrik

16.01.2013, 22:16

Nein. Es ist keine Formel zur Berechnung vo Primzahlen bekannt. Und nach etlichen Versuchen, eine zu finden, ist die mathematische Fachwelt überzeugt, dass es keine gibt. Gleichwohl wird vermutet, dass es eine unendliche Zahl Primzahlen gibt.

notizhelge

16.01.2013, 22:20

Nein. Es ist keine Formel zur Berechnung vo Primzahlen bekannt. [...]

Richtig.

Gleichwohl wird vermutet, dass es eine unendliche Zahl Primzahlen gibt.

Das wird nicht vermutet, sondern schon Euklid hat bewiesen, dass es unendlich viele Primzahlen gibt. http://de.wikipedia.org/wiki/Satz_von_Euklid

Kleinalrik

17.01.2013, 10:54

@notizhelge

Danke für die Richtigstellung.

HBenne

17.01.2013, 09:27

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

Wirklich brauchbare geschlossene Formeln gibt es dafür nicht. Aber Algorithmen, etwa das Sieb des Eratosthenes.

4k+1=p

Es gibt unendlich viele Primzahlen dieser Form. Aber nicht alle Zahlen dieser Form sind Primzahlen.

4k+3

Hier genau so. Allgemeiner: Es gibt unendlich viele Primzahlen der Form ak+b, wenn ggT(a,b)=1, a und b natürliche und n ganze Zahl.

HBenne

30.01.2013, 03:38

"und n ganze Zahl."

Da sollte nen k statt n stehen.

ceevee

16.01.2013, 22:42

Alle Primzahlen > 3 erfüllen entweder die Form p = 6n-1 oder p = 6n+1. Was es nicht gibt, ist eine Liste aller Primzahlen oder beispielsweise eine Funktion, mit der man effizient eine beliebig große Zahl in ihre Primfaktoren zerlegen kann.

JuriSeemann

16.01.2013, 22:46

Das ermitteln von Primzahlen ist eine beliebte Aufgabe für angehende Programmierer, es gibt natürlich Programme die beliebig hohe Primzahlen ermitteln können.

http://de.wikibooks.org/wiki/Primzahlen:_Programmbeispiele

Um das zu verstehen müsstest du allerdings die Basics von Java beherrschen.

gh7401

17.01.2013, 01:58

Das Produkt konsekutiver Primzahlen, vermehrt um 1 gibt sicher eine Primzahl..

rr1957

17.01.2013, 10:54

@gh7401

"vermehrt um 1 gibt sicher eine Primzahl.."

oder aber eine Zahl die einen Primfaktor hat der nicht zu den verwendeten Primzahlen gehört ... ( und ergibt damit eine neue Primzahl - aber normalerweise ist es eben nicht diese Zahl "Produkt plus 1" selbst )

zalto

01.01.2017, 15:32

@gh7401

3 * 5 + 1 = 16

5 * 7 + 1 = 36

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

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?

...zur Frage

Warum ist die wurzel aus einer primzahl nie eine natürliche zahl?

Joa meine frage steht ja oben aber nochmak hier Warum ist die wurzel aus einer primzahl nie eine natürliche zahl?

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

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

Wie kann man diesen Satz zu Primzahlen beweisen?

Erinnern Sie sich, dass eine Zahl p ∈ N \ {1} genau dann Primzahl heißt, wenn sie genau zwei Teiler hat, nämlich 1 und p. Beweisen Sie folgenden Satz:

Sei p ∈ N \ {1, 2} eine Primzahl. Dann gibt es k ∈ N0, sodass p = 4k + 1 oder p = 4k + 3

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

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

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

Die wurzel aus einer primzahl ist nie eine natürliche Zahl?

wieso ist das so ?

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