Pateiktas teigiamas sveikasis skaičius N, užduotis yra parašyti Python programą, kad patikrintumėte, ar skaičius yra Pirminis ar ne Python .

Pavyzdžiai:

  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“ programa, skirta patikrinti pirminį skaičių

Idėja išspręsti šią problemą yra kartoti visus skaičius, pradedant nuo 2 iki (N/2), naudojant už kilpą ir kiekvienam skaičiui patikrinkite, ar jis dalija N. Jei rasime bet kurį skaičių, kuris dalijasi, grąžinsime false. Jei neradome jokio skaičiaus tarp 2 ir N/2, kuris dalytų N, tai reiškia, kad N yra pirminis ir mes grąžinsime True.

num = 11 # If given number is greater than 1 if num>1: # Pakartokite nuo 2 iki n // 2 i diapazone (2, (skaičius//2)+1): # Jei skaičius dalijasi iš bet kurio skaičiaus tarp # 2 ir n / 2, jis nėra pirminis, jei ( skaičius % i) == 0: print(skaičius, 'nėra pirminis skaičius') break else: print(skaičius, 'yra pirminis skaičius') else: print(skaičius, 'nėra pirminis skaičius numeris')>>   
  Išvestis   
11 is a prime number 
    
    Laiko sudėtingumas     : O(n)   
    Pagalbinė erdvė:     O(1)  
  
 Raskite pirminius skaičius su vėliavėlės kintamuoju  
 
 Užuot tikrinę iki n, galime patikrinti iki √n, nes didesnis n koeficientas turi būti mažesnio jau patikrinto koeficiento kartotinis. Dabar pažiūrėkime pirmojo optimizavimo metodo kodą (t. y. tikrinimas iki √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): i diapazone (2, int(sqrt(n)) + 1): if (n % i == 0): pirminis_vėliava = 1 pertrauka if (pirminė_vėliava == 0): print('True' ) else: print('False') else: print('False') 
    
  Išvestis       Laiko sudėtingumas     :O(sqrt(n))   
    Pagalbinė erdvė:     O(1)  
  
    Patikrinkite pirminius skaičius naudodami rekursiją     
 
 Taip pat galime rasti skaičių pirminį arba nenaudojamą    rekursija    . Galime naudoti tikslią logiką, parodytą 2 metode, bet rekursiniu būdu.  
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)) 
    
  Išvestis   
True 
  
    Laiko sudėtingumas:     O(sqrt(n))   
    Pagalbinė erdvė     :O(sqrt(n))  
  
    Patikrinkite pagrindinio bandymo padalijimo metodą     
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)) 
    
  Išvestis   
True 
  
    Laiko sudėtingumas: O(sqrt(n))     
    Pagalbinė erdvė: O(sqrt(n))     
  
 
    Rekomenduojamas straipsnis –        Įvairių metodų, kaip rasti pirminį skaičių Python, analizė      
  
 
    „Python“ programa pirminiam skaičiui patikrinti. Naudojant ciklą, norint patikrinti dalijimąsi     
 
 Inicijuokite kintamąjį i į 2, kol i kvadratas yra mažesnis arba lygus n, patikrinkite, ar n dalijasi iš i. Jei n dalijasi iš i, grąžinkite False. Kitu atveju padidinkite i 1. Jei ciklas baigiamas neradus daliklio, grąžinkite 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 
    
  Išvestis   
True False 
  
 Laiko sudėtingumas: O(sqrt(n))   
 Pagalbinė erdvė: O(1)  
  
    „Python“ programa, skirta patikrinti pirminį skaičių naudojant matematikos modulį     
 
 Kode įgyvendinamas pagrindinis metodas, skirtas patikrinti, ar skaičius yra pirminis, ar ne, perkeliant visus skaičius nuo 2 iki sqrt(n)+1 ir patikrinant, ar n dalijasi iš kurio nors iš tų skaičių.  
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)) 
    
  Išvestis   
True 
  
    Laiko sudėtingumas:     O(sqrt(n))   
 Kodo sudėtingumas laike yra O(sqrt(n)), nes perkeliame visus skaičius diapazone nuo 2 iki sqrt(n)+1, kad patikrintume, ar n dalijasi iš kurio nors iš jų.  
  
    Pagalbinė erdvė:     O(1)   
 Kodo erdvės sudėtingumas yra O(1), nes naudojame tik pastovų atminties kiekį įvesties skaičiui n ir ciklo kintamiesiems saugoti.  
  
 „Python“ programa pirminiam numeriui patikrinti naudojant sympy.isprime() metodą  
 
 Sympy modulyje galime patikrinti, ar duotas skaičius n yra pirminis, ar ne, naudodami funkciją sympy.isprime(). n  <2   64   atsakymas yra galutinis; didesnės n reikšmės turi mažą tikimybę, kad iš tikrųjų yra pseudopradžiai.  
  
 
    N.B.:     Neigiami skaičiai (pvz., -13) nelaikomi pirminiu skaičiumi.  
  
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 
    
    Išvestis     
  
False True True 
 
    Laiko sudėtingumas:     O(sqrt(n)), kur n yra įvesties skaičius.   
    Pagalbinė erdvė:     O(1)