Eine Primzahl ist eine natürliche Zahl größer als 1 , die nur durch 1 und sich selbst teilbar ist. Die ersten paar Primzahlen sind: 2 3 5 7 11 13 17 19 23 …..

Einige interessante Fakten über Primzahlen 

• Zwei ist die einzige gerade Primzahl.
• Jede Primzahl kann in Form von 6n+1 oder 6n-1 dargestellt werden, mit Ausnahme der Primzahlen 2 und 3, wo n eine natürliche Zahl ist.
• Zwei und Drei sind nur zwei aufeinanderfolgende natürliche Zahlen, die Primzahlen sind.
• Goldbach-Vermutung: Jede gerade ganze Zahl größer als 2 kann als Summe zweier Primzahlen ausgedrückt werden.
• Satz von Wilson: Der Satz von Wilson besagt, dass eine natürliche Zahl p > 1 genau dann eine Primzahl ist

(p - 1) ! ≡  -1   mod p 
OR  (p - 1) ! ≡  (p-1) mod p

• Kleiner Satz von Fermat : Wenn n eine Primzahl ist, dann gilt für jedes a, 1 <= a < n,

an-1 ≡ 1 (mod n)
OR 
an-1 % n = 1

• Primzahlsatz : Die Wahrscheinlichkeit, dass eine gegebene, zufällig gewählte Zahl n eine Primzahl ist, ist umgekehrt proportional zu ihrer Anzahl an Ziffern oder zum Logarithmus von n.
• Lemoines Vermutung : Jede ungerade ganze Zahl größer als 5 kann als Summe einer ungeraden Primzahl (alle Primzahlen außer 2 sind ungerade) und einer geraden Halbprimzahl ausgedrückt werden. Eine Halbprimzahl ist ein Produkt zweier Primzahlen. Dies wird Lemoines Vermutung genannt.

Wie prüfen wir, ob eine Zahl eine Primzahl ist oder nicht? 

• Naive Lösung . 
  Eine naive Lösung besteht darin, alle Zahlen von 2 bis sqrt(n) zu durchlaufen und für jede Zahl zu prüfen, ob sie n teilt. Wenn wir eine teilbare Zahl finden, geben wir false zurück.

// A school method based C++ program to
// check if a number is prime
#include <bits/stdc++.h>
using namespace std;
 
// function check whether a number
// is prime or not
bool isPrime(int n)
{
    // Corner case
    if (n <= 1)
        return false;
 
    // Check from 2 to square root of n
    for (int i = 2; i <= sqrt(n); i++)
        if (n % i == 0)
            return false;
 
    return true;
}
 
// Driver Code
int main()
{
    isPrime(11) ? cout << " true\n" : cout << " false\n";
    return 0;
}

// A school method based Java program to
// check if a number is prime
import java.util.*;
import java.lang.*;
 
class GFG {
 
    // Check for number prime or not
    static boolean isPrime(int n)
    {
 
        // Check if number is less than
        // equal to 1
        if (n <= 1)
            return false;
 
        // Check if number is 2
        else if (n == 2)
            return true;
 
        // Check if n is a multiple of 2
        else if (n % 2 == 0)
            return false;
 
        // If not, then just check the odds
        for (int i = 3; i <= Math.sqrt(n); i += 2)
        {
            if (n % i == 0)
                return false;
        }
        return true;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        if (isPrime(19))
            System.out.println("true");
 
        else
            System.out.println("false");
    }
}
 
// This code is contributed by Ronak Bhensdadia

# A school method based Python3 program
# to check if a number is prime
 
# function check whether a number
# is prime or not
 
 
def isPrime(n):
 
    # Corner case
    if (n <= 1):
        return False
 
    # Check from 2 to n-1
    for i in range(2, n):
        if (n % i == 0):
            return False
 
    return True
 
 
# Driver Code
if isPrime(11):
    print("true")
else:
    print("false")
 
# This code is contributed by Sachin Bisht

// A school method based C# program to
// check if a number is prime
using System;
 
class GFG {
    // function check whether a
    // number is prime or not
    static bool isPrime(int n)
    {
        // Corner case
        if (n <= 1)
            return false;
 
        // Check from 2 to n-1
        for (int i = 2; i < n; i++)
            if (n % i == 0)
                return false;
 
        return true;
    }
 
    // Driver Code
    static void Main()
    {
        if (isPrime(11))
            Console.Write(" true");
 
        else
            Console.Write(" false");
    }
}
 
// This code is contributed by Sam007

<?php
// A school method based PHP program to
// check if a number is prime
 
// function check whether a number
// is prime or not
function isPrime($n)
{
    // Corner case
    if ($n <= 1)
        return false;
 
    // Check from 2 to n-1
    for ($i = 2; $i < $n; $i++)
        if ($n % $i == 0)
            return false;
 
    return true;
}
 
// Driver Code
if(isPrime(11))
    echo("true");
else
    echo("false");
 
// This code is contributed by Ajit.
?>

<script>
 
// A school method based Javascript program to
// check if a number is prime
 
  
// function check whether a number
// is prime or not
function isPrime(n)
{
    // Corner case
    if (n <= 1)
        return false;
  
    // Check from 2 to n-1
    for (let i = 2; i < n; i++)
        if (n % i == 0)
            return false;
  
    return true;
}
  
// Driver Code
 
    isPrime(11) ? document.write(" true" + "<br>") : document.write(" false" + "<br>");
 
// This code is contributed by Mayank Tyagi
 
</script>

wahr

Zeitkomplexität: O( ) 

Rekursion verwenden:

Rekursion kann auch verwendet werden, um zu prüfen, ob eine Zahl zwischen 2 bis n – 1 n teilt. Wenn wir eine teilbare Zahl finden, geben wir false zurück.

// C++ program to check whether a number
// is prime or not using recursion
#include <iostream>
using namespace std;
 
// function check whether a number
// is prime or not
bool isPrime(int n)
{
    static int i = 2;
 
    // corner cases
    if (n == 0 || n == 1) {
        return false;
    }
 
    // Checking Prime
    if (n == i)
        return true;
 
    // base cases
    if (n % i == 0) {
        return false;
    }
    i++;
    return isPrime(n);
}
 
// Driver Code
int main()
{
 
    isPrime(35) ? cout << " true\n" : cout << " false\n";
    return 0;
}
 
// This code is contributed by yashbeersingh42

// Java program to check whether a number
// is prime or not using recursion
class GFG{
     
static int i = 2;
  
// Function check whether a number
// is prime or not
public static boolean isPrime(int n)
{
     
    // Corner cases
    if (n == 0 || n == 1)
    {
        return false;
    }
   
    // Checking Prime
    if (n == i)
        return true;
         
    // Base cases
    if (n % i == 0)
    {
        return false;
    }
    i++;
    return isPrime(n);
}
 
// Driver Code  
public static void main(String[] args)
{
    if (isPrime(35))
    {
        System.out.println("true");
    }
    else
    {
        System.out.println("false");
    }
}
}
 
// This code is contributed by divyeshrabadiya07

# Python3 program to check whether a number
# is prime or not using recursion
 
# Function check whether a number
# is prime or not
def isPrime(n, i):
     
    # Corner cases
    if (n == 0 or n == 1):
        return False
     
    # Checking Prime 
    if (n == i):
        return True
     
    # Base cases
    if (n % i == 0):
        return False
     
    i += 1
     
    return isPrime(n, i)
 
# Driver Code
if (isPrime(35, 2)):
  print("true")
else:
  print("false")
   
#  This code is contributed by bunnyram19

// C# program to check whether a number
// is prime or not using recursion
using System;
class GFG {
     
    static int i = 2;
     
    // function check whether a number
    // is prime or not
    static bool isPrime(int n)
    {
      
        // corner cases
        if (n == 0 || n == 1) {
            return false;
        }
      
        // Checking Prime
        if (n == i)
            return true;
      
        // base cases
        if (n % i == 0) {
            return false;
        }
        i++;
        return isPrime(n);
    }
   
  static void Main() {
    if(isPrime(35))
    {
        Console.WriteLine("true");
    }
    else{
        Console.WriteLine("false");
    }
  }
}
 
// This code is contributed by divyesh072019

<script>
      // JavaScript program to check whether a number
      // is prime or not using recursion
 
      // function check whether a number
      // is prime or not
      function isPrime(n) {
        var i = 1;
 
        // corner cases
        if (n == 0 || n == 1) {
          return false;
        }
 
        // Checking Prime
        if (n == i) return true;
 
        // base cases
        if (n % i == 0) {
          return false;
        }
        i++;
        return isPrime(n);
      }
 
      // Driver Code
 
      isPrime(35) ? document.write(" true\n") : document.write(" false\n");
       
      // This code is contributed by rdtank.
    </script>

falsch

Zeitkomplexität : O(N) , Raumkomplexität : O(N) 

• Effiziente Lösungen 
  • Primzahltest | Set 1 (Einführung und Schulmethode)
  • Primzahltest | Set 2 (Fermat-Methode)
  • Primzahltest | Satz 3 (Miller–Rabin)
  • Primzahltest | Set 4 (Solovay-Straßen)
  • Lucas-Primalitätstest

Algorithmen, um alle Primzahlen kleiner als N zu finden. 

• Sieb des Eratosthenes
• Sieb des Eratosthenes in 0(n) Zeitkomplexität
• Segmentiertes Sieb
• Sieb von Sundaram
• Bitweises Sieb
• Aktuelle Artikel auf Sieve!

Weitere Probleme im Zusammenhang mit der Primzahl 

• Finden Sie zwei verschiedene Primzahlen mit einem gegebenen Produkt
• Geben Sie alle Primzahlen kleiner oder gleich N aus
• Rekursives Programm für Primzahlen
• Finden Sie zwei Primzahlen mit einer gegebenen Summe
• Finden Sie die höchste vorkommende Ziffer in Primzahlen in einem Bereich
• Primfaktorzerlegung mit Sieve O(log n) für mehrere Abfragen
• Programm zum Drucken aller Primfaktoren einer gegebenen Zahl
• Kleinster Primfaktor von Zahlen bis n
• Primfaktoren von LCM von Array-Elementen – GeeksforGeeks
• Programm für Goldbachs Vermutung
• Primzahlen und Fibonacci
• Zusammengesetzte Zahl
• Aktuelle Artikel zu Primzahlen!