Având în vedere un număr întreg pozitiv N, Sarcina este de a scrie un program Python pentru a verifica dacă numărul este Prim sau nu in Piton .

Exemple:

  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, ….}.>

Program Python pentru a verifica numărul prim

Ideea de a rezolva această problemă este să iterați toate numerele începând de la 2 la (N/2) folosind un pentru buclă iar pentru fiecare număr verificați dacă împarte N. Dacă găsim orice număr care împarte, returnăm fals. Dacă nu am găsit niciun număr între 2 și N/2 care să împartă N atunci înseamnă că N este prim și vom returna Adevărat.

num = 11 # If given number is greater than 1 if num>1: # Repetați de la 2 la n // 2 pentru i în intervalul (2, (num//2)+1): # Dacă num este divizibil cu orice număr între # 2 și n / 2, nu este prim dacă ( num % i) == 0: print(num, 'nu este un număr prim') break else: print(num, 'este un număr prim') else: print(num, 'nu este un prim număr')>>>  
  Ieșire  
11 is a prime number>
  
    Complexitatea timpului    : Pe)  
    Spatiu auxiliar:    O(1)
 
Găsiți numere prime cu o variabilă steag
În loc să verificăm până la n, putem verifica până la √n deoarece un factor mai mare al lui n trebuie să fie un multiplu al unui factor mai mic care a fost deja verificat. Acum să vedem codul pentru prima metodă de optimizare (adică verificarea până la √n)
 
 

Python3 
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): pentru i în interval(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')>
   
  Ieșire      Complexitatea timpului    :O(sqrt(n))  
    Spatiu auxiliar:    O(1)
 
    Verificați numerele prime utilizând recursiunea    
De asemenea, putem găsi numărul prim sau nefolosind  recursiunea  . Putem folosi logica exactă prezentată în metoda 2, dar într-un mod recursiv.
Python3 
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))>
   
  Ieșire  
True>
 
    Complexitatea timpului:    O(sqrt(n))  
    Spațiu auxiliar    :O(sqrt(n))
 
 

 
    Verificați metoda primului proces    
Python3 
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))>
   
  Ieșire  
True>
 
    Complexitatea timpului: O(sqrt(n))     
    Spațiu auxiliar: O(sqrt(n))    
  
    Articole recomandate –        Analiza diferitelor metode pentru a găsi numărul prim în Python     
 
    Programul Python pentru a verifica numărul prim Folosind o buclă while pentru a verifica divizibilitatea    
Inițializați o variabilă i la 2, în timp ce i pătratul este mai mic sau egal cu n, verificați dacă n este divizibil cu i. Dacă n este divizibil cu i, returnează False. În caz contrar, incrementați i cu 1. Dacă bucla se termină fără a găsi un divizor, returnați True.
Python3 
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>
   
  Ieșire  
True False>
 
Complexitatea timpului: O(sqrt(n))  
Spațiu auxiliar: O(1)
 
    Programul Python pentru a verifica numărul prim folosind modulul matematic    
Codul implementează o abordare de bază pentru a verifica dacă un număr este prim sau nu, parcurgând toate numerele de la 2 la sqrt(n)+1 și verificând dacă n este divizibil cu oricare dintre acele numere.
Python3 
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))>
   
  Ieșire  
True>
 
    Complexitatea timpului:    O(sqrt(n))  
Complexitatea de timp a codului este O(sqrt(n)) deoarece parcurgem toate numerele din intervalul de la 2 la sqrt(n)+1 pentru a verifica dacă n este divizibil cu oricare dintre ele.
 
    Spațiu auxiliar:    O(1)  
Complexitatea spațială a codului este O(1) deoarece folosim doar o cantitate constantă de memorie pentru a stoca numărul de intrare n și variabilele buclei.
 
Programul Python pentru a verifica numărul prim folosind metoda sympy.isprime().
În modulul sympy, putem testa dacă un anumit număr n este prim sau nu folosind funcția sympy.isprime(). Pentru n <264raspunsul este definitiv; valorile n mai mari au o probabilitate mică de a fi de fapt pseudoprime.
  
    N.B.:    Numerele negative (de exemplu, -13) nu sunt considerate numere prim.
 
Python3 
# 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>
  
    Ieșire    
 
False True True>
    Complexitatea timpului:    O(sqrt(n)), unde n este numărul de intrare.  
    Spațiu auxiliar:    O(1)