Gegeven een positief geheel getal N, is het de taak om een ​​Python-programma te schrijven om te controleren of het getal dat is Prime of niet erin Python .

Voorbeelden:

vijay filmacteur

  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-programma om priemgetal te controleren

Het idee om dit probleem op te lossen is om alle getallen vanaf 2 tot (N/2) te doorlopen met behulp van a for loop en controleer voor elk getal of het N deelt. Als we een getal vinden dat deelt, retourneren we false. Als we geen enkel getal tussen 2 en N/2 hebben gevonden dat N deelt, betekent dit dat N een priemgetal is en zullen we Waar retourneren.

num = 11 # If given number is greater than 1 if num>1: # Itereer van 2 tot n // 2 voor i in bereik(2, (num//2)+1): # Als num deelbaar is door een getal tussen # 2 en n / 2, is het geen priemgetal als ( num % i) == 0: print(num, 'is geen priemgetal') break else: print(num, 'is een priemgetal') else: print(num, 'is geen priemgetal nummer')>

11 is a prime number>

Tijdcomplexiteit : Op)
Hulpruimte: O(1)

Zoek priemgetallen met een vlagvariabele

In plaats van te controleren tot n, kunnen we controleren tot √n omdat een grotere factor van n een veelvoud moet zijn van een kleinere factor die al is gecontroleerd. Laten we nu de code bekijken voor de eerste optimalisatiemethode (dat wil zeggen controleren tot √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>

Tijdcomplexiteit :O(sqrt(n))
Hulpruimte: O(1)

Controleer priemgetallen met behulp van recursie

We kunnen ook het priemgetal vinden of niet gebruiken herhaling . We kunnen de exacte logica gebruiken die wordt getoond in methode 2, maar op een recursieve manier.

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>

Tijdcomplexiteit: O(sqrt(n))
Hulpruimte :O(sqrt(n))

Controleer de Prime Trial Division-methode

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>

Tijdcomplexiteit: O(sqrt(n))
Hulpruimte: O(sqrt(n))

Aanbevolen artikel – Analyse van verschillende methoden om priemgetallen in Python te vinden

Python-programma om priemgetallen te controleren Een while-lus gebruiken om de deelbaarheid te controleren

Initialiseer een variabele i tot 2. Terwijl i kwadraat kleiner is dan of gelijk is aan n, controleer dan of n deelbaar is door i. Als n deelbaar is door i, retourneert u False. Anders verhoogt u i met 1. Als de lus eindigt zonder een deler te vinden, retourneert u True.

in een string werpen

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>

Tijdcomplexiteit: O(sqrt(n))
Hulpruimte: O(1)

Python-programma om priemgetallen te controleren met behulp van de wiskundemodule

De code implementeert een basisaanpak om te controleren of een getal een priemgetal is of niet, door alle getallen van 2 tot sqrt(n)+1 te doorlopen en te controleren of n deelbaar is door een van die getallen.

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>

Tijdcomplexiteit: O(sqrt(n))
De tijdscomplexiteit van de code is O(sqrt(n)) omdat we alle getallen in het bereik van 2 tot sqrt(n)+1 doorlopen om te controleren of n deelbaar is door een van deze getallen.

Hulpruimte: O(1)
De ruimtecomplexiteit van de code is O(1) omdat we alleen een constante hoeveelheid geheugen gebruiken om het invoernummer n en de lusvariabelen op te slaan.

Python-programma om priemgetallen te controleren met behulp van de sympy.isprime()-methode

In de sympy-module kunnen we testen of een bepaald getal n een priemgetal is of niet met behulp van de functie sympy.isprime(). Voor n <2⁶⁴het antwoord is definitief; grotere n-waarden hebben een kleine kans dat ze daadwerkelijk pseudopriemgetallen zijn.

N.B.: Negatieve getallen (bijvoorbeeld -13) worden niet als priemgetal beschouwd.

gelijk aan Java

# 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>

Uitvoer

False True True>

Tijdcomplexiteit: O(sqrt(n)), waarbij n het invoernummer is.
Hulpruimte: O(1)