Primzahltest | Set 1 (Einführung und Schulmethode)
Prüfen Sie bei einer positiven Ganzzahl, ob die Zahl eine Primzahl ist oder nicht. Eine Primzahl ist eine natürliche Zahl größer als 1, die außer 1 und sich selbst keine positiven Teiler hat. Beispiele für die ersten paar Primzahlen sind {2, 3, 5,
Beispiele:
Input: n = 11 Output: true Input: n = 15 Output: false Input: n = 1 Output: false
Schulmethode
Eine einfache Lösung besteht darin, alle Zahlen von 2 bis n-1 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.
Unten ist die Implementierung dieser Methode.
C++
// A school method based C++ program to check if a // number is prime #include <bits/stdc++.h> using namespace std; 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 Program to test above function int main() { isPrime(11)? cout << " true\n": cout << " false\n"; isPrime(15)? cout << " true\n": cout << " false\n"; return 0; }
Java
// A school method based JAVA program // to check if a number is prime class GFG { static boolean 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 Program public static void main(String args[]) { if(isPrime(11)) System.out.println(" true"); else System.out.println(" false"); if(isPrime(15)) System.out.println(" true"); else System.out.println(" false"); } } // This code is contributed // by Nikita Tiwari.
Python3
# A school method based Python3 # program to check if a number # is prime 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 Program to test above function print("true") if isPrime(11) else print("false") print("true") if isPrime(14) else print("false") # This code is contributed by Smitha Dinesh Semwal
C#
// A optimized school method based C# // program to check if a number is prime using System; namespace prime { public class GFG { public static bool isprime(int n) { // Corner cases if (n <= 1) return false; for (int i = 2; i < n; i++) if (n % i == 0) return false; return true; } // Driver program public static void Main() { if (isprime(11)) Console.WriteLine("true"); else Console.WriteLine("false"); if (isprime(15)) Console.WriteLine("true"); else Console.WriteLine("false"); } } } // This code is contributed by Sam007
PHP
<?php // A school method based PHP // program to check if a number // is prime 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 $tet = isPrime(11) ? " true\n" : " false\n"; echo $tet; $tet = isPrime(15) ? " true\n" : " false\n"; echo $tet; // This code is contributed by m_kit ?>
Javascript
<script> // A school method based Javascript program to check if a // number is prime 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 Program to test above function isPrime(11)? document.write(" true" + "<br>"): document.write(" false" + "<br>"); isPrime(15)? document.write(" true" + "<br>"): document.write(" false" + "<br>"); // This code is contributed by Mayank Tyagi </script>
Ausgabe :
true false
Die Zeitkomplexität dieser Lösung ist O(n)
Optimierte Schulmethode
Wir können folgende Optimierungen vornehmen:
- Anstatt bis n zu prüfen, können wir bis √n prüfen, da ein größerer Faktor von n ein Vielfaches eines bereits geprüften kleineren Faktors sein muss.
- Der Algorithmus kann weiter verbessert werden, indem beobachtet wird, dass alle Primzahlen die Form 6k ± 1 haben, mit Ausnahme von 2 und 3. Dies liegt daran, dass alle ganzen Zahlen als (6k + i) für eine ganze Zahl k und für i = - ausgedrückt werden können. 1, 0, 1, 2, 3 oder 4; 2 teilt (6k + 0), (6k + 2), (6k + 4); und 3 teilt (6k + 3). Eine effizientere Methode besteht also darin, zu testen, ob n durch 2 oder 3 teilbar ist, und dann alle Zahlen der Form 6k ± 1 zu überprüfen. (Quelle: Wikipedia )
Falls Sie an Live-Kursen mit Experten teilnehmen möchten , beziehen Sie sich bitte auf DSA Live-Kurse für Berufstätige und Competitive Programming Live for Students .