Étant donné un entier positif N, la tâche consiste à écrire un programme Python pour vérifier si le nombre est Prime ou pas dans Python .

Exemples:

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

Programme Python pour vérifier le nombre premier

L'idée pour résoudre ce problème est de parcourir tous les nombres allant de 2 à (N/2) en utilisant un pour la boucle et pour chaque nombre, vérifiez s'il divise N. Si nous trouvons un nombre qui divise, nous renvoyons faux. Si nous n’avons trouvé aucun nombre entre 2 et N/2 qui divise N alors cela signifie que N est premier et nous renverrons True.

num = 11 # If given number is greater than 1 if num>1: # Itérer de 2 à n // 2 pour i in range(2, (num//2)+1) : # Si num est divisible par n'importe quel nombre entre # 2 et n / 2, il n'est pas premier si ( num % i) == 0 : print(num, 'n'est pas un nombre premier') break else: print(num, 'est un nombre premier') else: print(num, 'n'est pas un nombre premier numéro')>

11 is a prime number>

Complexité temporelle : Sur)
Espace auxiliaire : O(1)

Trouver des nombres premiers avec une variable indicateur

Au lieu de vérifier jusqu'à n, nous pouvons vérifier jusqu'à √n car un facteur plus grand de n doit être un multiple d'un facteur plus petit qui a déjà été vérifié. Voyons maintenant le code de la première méthode d'optimisation (c'est-à-dire vérifier jusqu'à √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) : pour i dans 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>

Complexité temporelle :O(carré(n))
Espace auxiliaire : O(1)

Vérifier les nombres premiers à l'aide de la récursion

On peut aussi trouver le nombre premier ou non en utilisant récursivité . Nous pouvons utiliser la logique exacte présentée dans la méthode 2 mais de manière récursive.

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>

Complexité temporelle : O(sqrt(n))
Espace auxiliaire :O(carré(n))

Vérifiez la méthode Prime Trial Division

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>

Complexité temporelle : O(sqrt(n))
Espace auxiliaire : O(sqrt(n))

Article recommandé – Analyse de différentes méthodes pour trouver un nombre premier en Python

Programme Python pour vérifier les nombres premiers Utilisation d'une boucle while pour vérifier la divisibilité

Initialisez une variable i à 2, tandis que i au carré est inférieur ou égal à n, vérifiez si n est divisible par i. Si n est divisible par i, renvoie False. Sinon, incrémentez i de 1. Si la boucle se termine sans trouver de diviseur, renvoyez True.

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>

Complexité temporelle : O(sqrt(n))
Espace auxiliaire : O(1)

Programme Python pour vérifier les nombres premiers à l'aide du module mathématique

Le code implémente une approche de base pour vérifier si un nombre est premier ou non, en parcourant tous les nombres de 2 à sqrt(n)+1 et en vérifiant si n est divisible par l'un de ces nombres.

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>

Complexité temporelle : O(sqrt(n))
La complexité temporelle du code est O(sqrt(n)) car nous parcourons tous les nombres compris entre 2 et sqrt(n)+1 pour vérifier si n est divisible par l'un d'entre eux.

Espace auxiliaire : O(1)
La complexité spatiale du code est O(1) car nous utilisons uniquement une quantité constante de mémoire pour stocker le numéro d'entrée n et les variables de boucle.

Programme Python pour vérifier les nombres premiers à l'aide de la méthode sympy.isprime()

Dans le module sympy, nous pouvons tester si un nombre n donné est premier ou non en utilisant la fonction sympy.isprime(). Pour n <2⁶⁴la réponse est définitive ; des valeurs n plus grandes ont une faible probabilité d'être réellement des pseudo-premiers.

N.B. : Les nombres négatifs (par exemple -13) ne sont pas considérés comme des nombres premiers.

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

Sortir

False True True>

Complexité temporelle : O(sqrt(n)), où n est le numéro d'entrée.
Espace auxiliaire : O(1)