Bei einer positiven Ganzzahl N besteht die Aufgabe darin, ein Python-Programm zu schreiben, um zu überprüfen, ob die Zahl vorhanden ist Prime oder nicht drin Python .

Beispiele:

  Input:   n = 11   Output:   True   Input:   n = 1   Output:   False   Explanation:   A prime number is a natural number greater than 1 that  has no positive divisors other than 1 and itself.  The first few prime numbers are {2, 3, 5, 7, 11, ….}.>

Python-Programm zur Überprüfung von Primzahlen

Die Idee zur Lösung dieses Problems besteht darin, alle Zahlen von 2 bis (N/2) mit a zu durchlaufen for-Schleife und prüfen Sie für jede Zahl, ob sie N teilt. Wenn wir eine Zahl finden, die teilbar ist, geben wir false zurück. Wenn wir keine Zahl zwischen 2 und N/2 gefunden haben, die N teilt, bedeutet das, dass N eine Primzahl ist und wir werden „True“ zurückgeben.

num = 11 # If given number is greater than 1 if num>1: # Iteriere von 2 bis n // 2 für i in range(2, (num//2)+1): # Wenn num durch eine beliebige Zahl zwischen # 2 und n / 2 teilbar ist, ist es keine Primzahl, wenn ( num % i) == 0: print(num, 'ist keine Primzahl') break else: print(num, 'ist eine Primzahl') else: print(num, 'ist keine Primzahl Nummer')>

11 is a prime number>

Zeitkomplexität : An)
Nebenraum: O(1)

Finden Sie Primzahlen mit einer Flag-Variablen

Anstatt bis n zu prüfen, können wir bis √n prüfen, da ein größerer Faktor von n ein Vielfaches eines kleineren Faktors sein muss, der bereits geprüft wurde. Sehen wir uns nun den Code für die erste Optimierungsmethode an (d. h. Prüfung bis √n).

schönstes Lächeln

from math import sqrt # n is the number to be check whether it is prime or not n = 1 # this flag maintains status whether the n is prime or not prime_flag = 0 if(n>1): für i in range(2, int(sqrt(n)) + 1): if (n % i == 0): prime_flag = 1 break if (prime_flag == 0): print('True' ) else: print('False') else: print('False')>

False>

Zeitkomplexität :O(sqrt(n))
Nebenraum: O(1)

Überprüfen Sie Primzahlen mithilfe der Rekursion

Wir können auch die Zahl Primzahl finden oder nicht verwenden Rekursion . Wir können die exakte in Methode 2 gezeigte Logik verwenden, jedoch auf rekursive Weise.

from math import sqrt def Prime(number,itr): #prime function to check given number prime or not if itr == 1: #base condition return True if number % itr == 0: #if given number divided by itr or not return False if Prime(number,itr-1) == False: #Recursive function Call return False return True num = 13 itr = int(sqrt(num)+1) print(Prime(num,itr))>

True>

Zeitkomplexität: O(sqrt(n))
Hilfsraum :O(sqrt(n))

Schauen Sie sich die Prime Trial Division-Methode an

def is_prime_trial_division(n): # Check if the number is less than # or equal to 1, return False if it is if n <= 1: return False # Loop through all numbers from 2 to # the square root of n (rounded down to the nearest integer) for i in range(2, int(n**0.5)+1): # If n is divisible by any of these numbers, return False if n % i == 0: return False # If n is not divisible by any of these numbers, return True return True # Test the function with n = 11 print(is_prime_trial_division(11))>

True>

Zeitkomplexität: O(sqrt(n))
Hilfsraum: O(sqrt(n))

Empfohlener Artikel – Analyse verschiedener Methoden zum Finden von Primzahlen in Python

Python-Programm zum Überprüfen von Primzahlen. Verwenden einer While-Schleife zum Überprüfen der Teilbarkeit

Initialisieren Sie eine Variable i auf 2. Während das Quadrat von i kleiner oder gleich n ist, prüfen Sie, ob n durch i teilbar ist. Wenn n durch i teilbar ist, wird „False“ zurückgegeben. Andernfalls erhöhen Sie i um 1. Wenn die Schleife beendet wird, ohne dass ein Teiler gefunden wird, wird „True“ zurückgegeben.

import math def is_prime(n): if n < 2: return False i = 2 while i*i <= n: if n % i == 0: return False i += 1 return True print(is_prime(11)) # True print(is_prime(1)) # False>

True False>

Zeitkomplexität: O(sqrt(n))
Hilfsraum: O(1)

Python-Programm zum Überprüfen von Primzahlen mithilfe des Mathematikmoduls

Der Code implementiert einen grundlegenden Ansatz zur Prüfung, ob eine Zahl eine Primzahl ist oder nicht, indem er alle Zahlen von 2 bis sqrt(n)+1 durchläuft und prüft, ob n durch eine dieser Zahlen teilbar ist.

import math def is_prime(n): if n <= 1: return False for i in range(2, int(math.sqrt(n)) + 1): if n % i == 0: return False return True n = 11 print(is_prime(n))>

True>

Zeitkomplexität: O(sqrt(n))
Die zeitliche Komplexität des Codes beträgt O(sqrt(n)), da wir alle Zahlen im Bereich von 2 bis sqrt(n)+1 durchlaufen, um zu prüfen, ob n durch eine dieser Zahlen teilbar ist.

Was ist in Python?

Hilfsraum: O(1)
Die räumliche Komplexität des Codes beträgt O(1), da wir nur eine konstante Speichermenge zum Speichern der Eingabezahl n und der Schleifenvariablen verwenden.

Python-Programm zur Überprüfung von Primzahlen mit der Methode sympy.isprime()

Im Sympy-Modul können wir mit der Funktion sympy.isprime() testen, ob eine gegebene Zahl n eine Primzahl ist oder nicht. Für n <2⁶⁴die Antwort ist endgültig; Bei größeren n-Werten besteht eine geringe Wahrscheinlichkeit, dass es sich tatsächlich um Pseudoprimzahlen handelt.

Hinweis: Negative Zahlen (z. B. -13) gelten nicht als Primzahlen.

# Python program to check prime number # using sympy.isprime() method # importing sympy module from sympy import * # calling isprime function on different numbers geek1 = isprime(30) geek2 = isprime(13) geek3 = isprime(2) print(geek1) # check for 30 is prime or not print(geek2) # check for 13 is prime or not print(geek3) # check for 2 is prime or not # This code is contributed by Susobhan Akhuli>

Ausgabe

False True True>

Zeitkomplexität: O(sqrt(n)), wobei n die Eingabezahl ist.
Hilfsraum: O(1)