Was sind Primzahlen?
A Primzahl ist definiert als eine natürliche Zahl größer als 1 und ist nur durch 1 und sich selbst teilbar.
Mit anderen Worten: Die Primzahl ist eine positive ganze Zahl größer als 1, die genau zwei Faktoren hat, 1 und die Zahl selbst. Die ersten paar Primzahlen sind 2, 3, 5, 7, 11, 13, 17, 19, 23. . .
Notiz: 1 ist weder eine Primzahl noch eine zusammengesetzte Zahl. Die übrigen Zahlen, mit Ausnahme von 1, werden als Primzahlen und zusammengesetzte Zahlen klassifiziert.

Primzahlen
Einige interessante Fakten über Primzahlen:
- Bis auf 2, das ist das kleinste Primzahl und die einzige gerade Primzahl, alle Primzahlen sind ungerade Zahlen.
- Jede Primzahl kann in der Form dargestellt werden 6n + 1 oder 6n – 1 außer den Primzahlen 2 Und 3 , wobei n eine beliebige natürliche Zahl ist.
- 2 und 3 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.
- Wilson-Theorem : Der Satz von Wilson besagt, dass eine natürliche Zahl p> 1 genau dann eine Primzahl ist, wenn
(S. – 1) ! ≡ -1 gegen p
ODER,
(S. – 1) ! ≡ (p-1) mod p
- Fermats kleiner Satz : Wenn n eine Primzahl ist, dann gilt für jedes a 1 ≤ a
An-1≡ 1 (mod n)
ODER,
An-1% n = 1
- Primzahlsatz : Die Wahrscheinlichkeit, dass eine gegebene, zufällig ausgewä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 nennt man Lemoines Vermutung.
Eigenschaften von Primzahlen:
- Jede Zahl größer als 1 kann durch mindestens eine Primzahl geteilt werden.
- Jede gerade positive ganze Zahl größer als 2 kann als Summe zweier Primzahlen ausgedrückt werden.
- Außer 2 sind alle anderen Primzahlen ungerade. Mit anderen Worten: Wir können sagen, dass 2 die einzige gerade Primzahl ist.
- Zwei Primzahlen sind immer teilerfremd zueinander.
- Jede zusammengesetzte Zahl kann in Primfaktoren zerlegt werden, und alle einzeln sind von Natur aus einzigartig.
Primzahlen und Koprimzahlen:
Es ist wichtig, zwischen zu unterscheiden Primzahlen Und Koprimzahlen . Nachfolgend sind die Unterschiede zwischen Primzahlen und Koprimzahlen aufgeführt.
- Koprimzahlzahlen werden immer als Paar betrachtet, wohingegen eine Primzahl eine einzelne Zahl ist.
- Koprimzahlen sind Zahlen, die außer 1 keinen gemeinsamen Teiler haben. Im Gegensatz dazu haben Primzahlen eine solche Bedingung nicht.
- Eine Koprimzahl kann entweder eine Primzahl oder eine zusammengesetzte Zahl sein, ihr größter gemeinsamer Faktor (GCF) muss jedoch immer 1 sein. Im Gegensatz zu zusammengesetzten Zahlen haben Primzahlen nur zwei Faktoren, 1 und die Zahl selbst.
- Beispiel für Co-Prime: 13 und 15 sind Koprimzahlen. Die Faktoren von 13 sind 1 und 13 und die Faktoren von 15 sind 1, 3 und 5. Wir können sehen, dass sie nur 1 als gemeinsamen Faktor haben, daher sind sie Koprimzahlen.
- Beispiel für Primzahl: Einige Beispiele für Primzahlen sind 2, 3, 5, 7 und 11 usw.
Wie kann man überprüfen, ob eine Zahl eine Primzahl ist oder nicht?
Naiver Ansatz: Der naive Ansatz besteht darin
Iterieren Sie von 2 bis (n-1) und prüfen Sie, ob sich eine Zahl in diesem Bereich teilt N . Wenn sich die Zahl teilt N , dann ist es keine Primzahl.
Zeitkomplexität: AN)
Hilfsraum: O(1)
Naiver Ansatz (rekursiv): Rekursion kann auch verwendet werden, um zu überprüfen, ob eine Zahl zwischen 2 durch n – 1 teilt n. Wenn wir eine Zahl finden, die sich teilt, geben wir false zurück.
Nachfolgend finden Sie die Umsetzung der obigen Idee:
C++
// C++ program to check whether a number> // is prime or not using recursion> #include> 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
'> : cout <<>' false
'>;> >return> 0;> }> > // This code is contributed by yashbeersingh42> |
>
>
Java
// Java program to check whether a number> // is prime or not using recursion> import> java.io.*;> > 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
# 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#
// 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> |
>
>
Javascript
> >// JavaScript program to check whether a number> >// is prime or not using recursion> > >// function check whether a number> >// is prime or not> >var> i = 2;> > >function> isPrime(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> > >isPrime(35) ? document.write(>' true
'>) : document.write(>' false
'>);> > >// This code is contributed by rdtank.> >> |
Objekt zu jsonobject Java
>
>Ausgabe
false>
Zeitkomplexität: AN)
Hilfsraum: O(N), wenn wir den Rekursionsstapel betrachten. Ansonsten ist es O(1).
Effizienter Ansatz: Eine effiziente Lösung ist:
Iteriere alle Zahlen von 2 zur Quadratwurzel von N und prüfen Sie für jede Zahl, ob sie n teilt [denn wenn eine Zahl ausgedrückt wird als n = xy und eines von x oder y ist größer als die Wurzel von n, das andere muss kleiner als der Wurzelwert sein]. Wenn wir eine Zahl finden, die sich teilt, geben wir false zurück.
Unten ist die Implementierung:
C++14
// A school method based C++ program to> // check if a number is prime> #include> 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
'> : cout <<>'false
'>;> >return> 0;> }> |
>
>
Java
// A school method based Java program to> // check if a number is prime> import> java.lang.*;> import> java.util.*;> > 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> |
>
>
Python3
# A school method based Python3 program> # to check if a number is prime> > > # import sqrt from math module> from> math>import> sqrt> > > > # Function check whether a number> # is prime or not> def> isPrime(n):> > ># Corner case> >if> (n <>=> 1>):> >return> False> > ># Check from 2 to sqrt(n)> >for> i>in> range>(>2>,>int>(sqrt(n))>+>1>):> >if> (n>%> i>=>=> 0>):> >return> False> > >return> True> > > # Driver Code> if> __name__>=>=> '__main__'>:> >if> isPrime(>11>):> >print>(>'true'>)> >else>:> >print>(>'false'>)> > # This code is contributed by Sachin Bisht> |
>
>
C#
// 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 sqrt(n)> >for> (>int> i = 2; i <= Math.Sqrt(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> |
>
>
Javascript
Zeile und Spalte
// 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 if (n % i == 0) return false; return true; } // Driver Code isPrime(11) ? console.log(' true') : console.log(' false'); // This code is contributed by Mayank Tyagi> |
>
>
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. ?>> |
>
>Ausgabe
true>
Zeitkomplexität: O(sqrt(n))
Nebenraum: O(1)
Ein weiterer effizienter Ansatz: Um zu überprüfen, ob die Zahl eine Primzahl ist oder nicht, befolgen Sie die folgende Idee:
Wir werden uns mit einigen Zahlen wie 1, 2, 3 und den durch 2 und 3 teilbaren Zahlen in einzelnen Fällen und für die übrigen Zahlen befassen. Iterieren Sie von 5 bis sqrt(n) und prüfen Sie bei jeder Iteration, ob (dieser Wert) oder (dieser Wert + 2) n teilt oder nicht, und erhöhen Sie den Wert um 6 [da jede Primzahl als 6n+1 oder 6n-1 ausgedrückt werden kann ]. Wenn wir eine Zahl finden, die sich teilt, geben wir false zurück.
Nachfolgend finden Sie die Umsetzung der obigen Idee:
C++
// A school method based C++ program to> // check if a number is prime> #include> using> namespace> std;> > // Function check whether a number> // is prime or not> bool> isPrime(>int> n)> > > // Driver Code> int> main()> {> >isPrime(11) ? cout <<>'true
'> : cout <<>'false
'>;> >return> 0;> }> // This code is contributed by Suruchi kumari> |
>
>
C
// A school method based C program to> // check if a number is prime> #include> #include> > // Function check whether a number> // is prime or not> int> isPrime(>int> n)> n % 3 == 0)> >return> 0;> >// Check from 5 to square root of n> >// Iterate i by (i+6)> >for> (>int> i = 5; i * i <= n; i = i + 6)> >if> (n % i == 0> > // Driver Code> int> main()> {> >if> (isPrime(11) == 1)> >printf>(>'true
'>);> >else> >printf>(>'false
'>);> >return> 0;> }> // This code is contributed by Suruchi Kumari> |
>
>
Java
// Java program to check whether a number> import> java.lang.*;> import> java.util.*;> > class> GFG {> > >// Function check whether a number> >// is prime or not> >public> static> boolean> isPrime(>int> n)> >> >if> (n <=>1>)> >return> false>;> > >// Check if n=2 or n=3> >if> (n ==>2> > > >// Driver Code> >public> static> void> main(String[] args)> >{> >if> (isPrime(>11>)) {> >System.out.println(>'true'>);> >}> >else> {> >System.out.println(>'false'>);> >}> >}> }> > // This code is contributed by Sayan Chatterjee> |
>
>
Python3
numpy bedeuten
import> math> > def> is_prime(n:>int>)>->>>bool>:> > ># Check if n=1 or n=0> >if> n <>=> 1>:> >return> 'false'> > ># Check if n=2 or n=3> >if> n>=>=> 2> or> n>=>=> 3>:> >return> 'true'> > ># Check whether n is divisible by 2 or 3> >if> n>%> 2> =>=> 0> or> n>%> 3> =>=> 0>:> >return> 'false'> > ># Check from 5 to square root of n> ># Iterate i by (i+6)> >for> i>in> range>(>5>,>int>(math.sqrt(n))>+>1>,>6>):> >if> n>%> i>=>=> 0> or> n>%> (i>+> 2>)>=>=> 0>:> >return> 'false'> > >return> 'true'> > if> __name__>=>=> '__main__'>:> >print>(is_prime(>11>))> |
>
>
C#
// C# program to check whether a number> using> System;> class> GFG {> > >// Function check whether a number> >// is prime or not> >public> static> bool> isPrime(>int> n)> >> > >// Driver Code> >public> static> void> Main(String[] args)> >{> >if> (isPrime(11)) {> >Console.WriteLine(>'true'>);> >}> >else> {> >Console.WriteLine(>'false'>);> >}> >}> }> > // This code is contributed by Abhijeet> // Kumar(abhijeet_19403)> |
>
>
Javascript
// A school method based JS program to> // check if a number is prime> > > // Function check whether a number> // is prime or not> function> isPrime(n)> n % (i + 2) == 0)> >return> false>;> > >return> true>;> > > // Driver Code> isPrime(11) ? console.log(>'true'>) : console.log(>'false'>);> > > // This code is contributed by phasing17> |
>
>Ausgabe
true>
Zeitkomplexität: O(sqrt(n))
Nebenraum: O(1)
Effiziente Lösungen
- Primzahltest | Set 1 (Einführung und Schulmethode)
- Primzahltest | Satz 2 (Fermat-Methode)
- Primzahltest | Satz 3 (Miller–Rabin)
- Primzahltest | Set 4 (Solovay-Straßen)
- Lucas-Primalitätstest
Algorithmen zum Finden aller Primzahlen kleiner als N.
- Sieb des Eratosthenes
- Sieb des Eratosthenes in 0(n)-Zeitkomplexität
- Segmentiertes Sieb
- Sieb von Sundaram
- Bitweises Sieb
- Aktuelle Artikel zu Sieve!
Weitere Probleme im Zusammenhang mit der Primzahl
- Finden Sie zwei verschiedene Primzahlen mit A gegebenes Produkt
- Geben Sie alle Primzahlen aus, die kleiner oder gleich N sind
- Rekursives Programm für Primzahlen
- Finden Sie zwei Primzahlen mit A gegebene Summe
- Finden Sie die am häufigsten vorkommende Ziffer in Primzahlen in einem Bereich
- Primfaktorisierung mit Sieve O(log n) für mehrere Abfragen
- Programm zum Drucken aller Primfaktoren einer bestimmten Zahl
- Kleinster Primfaktor von Zahlen bis n
- Primfaktoren der LCM von Array-Elementen – techcodeview.com
- Programm für Goldbachs Vermutung
- Primzahlen und Fibonacci
- Zusammengesetzte Zahl
- Aktuelle Artikel zum Thema Primzahlen!