Givet et positivt heltal N, er opgaven at skrive et Python-program for at kontrollere, om tallet er Prime eller ej i Python .

Eksempler:

  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-program til at kontrollere primtal

Ideen til at løse dette problem er at gentage alle tallene fra 2 til (N/2) ved hjælp af en for sløjfe og for hvert tal skal du kontrollere, om det deler N. Hvis vi finder et tal, der deler, returnerer vi falsk. Hvis vi ikke fandt noget tal mellem 2 og N/2, som deler N, betyder det, at N er primtal, og vi vil returnere Sand.

num = 11 # If given number is greater than 1 if num>1: # Iterer fra 2 til n // 2 for i i området(2, (tal//2)+1): # Hvis num er deleligt med et hvilket som helst tal mellem # 2 og n / 2, er det ikke primtal, hvis ( num % i) == 0: print(tal, 'er ikke et primtal') break else: print(tal, 'er et primtal') else: print(tal, 'er ikke et primtal') nummer') 

11 is a prime number 

Tidskompleksitet : På)
Hjælpeplads: O(1)

Find primtal med en flagvariabel

I stedet for at kontrollere indtil n, kan vi kontrollere indtil √n, fordi en større faktor af n skal være et multiplum af en mindre faktor, der allerede er kontrolleret. Lad os nu se koden for den første optimeringsmetode (dvs. kontrol til √n)

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): for 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 

Tidskompleksitet :O(sqrt(n))
Hjælpeplads: O(1)

Tjek primtal ved hjælp af rekursion

Vi kan også finde tallet primtal eller ikke bruge rekursion . Vi kan bruge den nøjagtige logik vist i metode 2, men på en rekursiv måde.

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 

Tidskompleksitet: O(sqrt(n))
Hjælpeplads :O(sqrt(n))

Tjek Prime Trial Division Method

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 

Tidskompleksitet: O(sqrt(n))
Hjælpeplads: O(sqrt(n))

Anbefalet artikel – Analyse af forskellige metoder til at finde primtal i Python

Python-program til at kontrollere primtal Brug af en while-løkke til at kontrollere delelighed

Initialiser en variabel i til 2. Mens i i anden er mindre end eller lig med n, skal du kontrollere, om n er delelig med i. Hvis n er delelig med i, returneres False. Ellers øges i med 1. Hvis løkken afsluttes uden at finde en divisor, returneres Sand.

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 

Tidskompleksitet: O(sqrt(n))
Hjælpeplads: O(1)

Python-program til at kontrollere primtal ved hjælp af matematikmodul

Koden implementerer en grundlæggende tilgang til at kontrollere, om et tal er primtal eller ej, ved at krydse alle tallene fra 2 til sqrt(n)+1 og kontrollere, om n er delelig med nogen af ​​disse tal.

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 

Tidskompleksitet: O(sqrt(n))
Kodens tidskompleksitet er O(sqrt(n)), fordi vi krydser alle tal i intervallet 2 til sqrt(n)+1 for at kontrollere, om n er delelig med nogen af ​​dem.

Hjælpeplads: O(1)
Kodens rumkompleksitet er O(1), fordi vi kun bruger en konstant mængde hukommelse til at gemme inputnummeret n og sløjfevariablerne.

Python-program til at kontrollere primtal ved hjælp af sympy.isprime()-metoden

I sympy-modulet kan vi teste, om et givet tal n er primtal eller ej ved hjælp af sympy.isprime()-funktionen. For n <2 ⁶⁴ svaret er endeligt; større n-værdier har en lille sandsynlighed for rent faktisk at være pseudoprimer.

N.B.: Negative tal (f.eks. -13) betragtes ikke som primtal.

# 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 

Produktion

False True True 

Tidskompleksitet: O(sqrt(n)), hvor n er inputnummeret.
Hjælpeplads: O(1)