Dato un intero positivo N, il compito è scrivere un programma Python per verificare se il numero lo è Primo o non dentro Pitone .

Esempi:

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

Programma Python per controllare i numeri primi

L'idea per risolvere questo problema è scorrere tutti i numeri a partire da 2 fino a (N/2) utilizzando a per ciclo e per ogni numero controlla se divide N. Se troviamo un numero qualsiasi che divide, restituiamo false. Se non troviamo nessun numero compreso tra 2 e N/2 che divide N allora significa che N è primo e restituiremo True.

num = 11 # If given number is greater than 1 if num>1: # Itera da 2 a n // 2 for i in range(2, (num//2)+1): # Se num è divisibile per qualsiasi numero compreso tra # 2 e n / 2, non è primo if ( num % i) == 0: print(num, 'non è un numero primo') break else: print(num, 'è un numero primo') else: print(num, 'non è un numero primo numero')>

11 is a prime number>

Complessità temporale : SU)
Spazio ausiliario: O(1)

Trova i numeri primi con una variabile flag

Invece di controllare fino a n, possiamo controllare fino a √n perché un fattore più grande di n deve essere multiplo di un fattore più piccolo che è già stato controllato. Vediamo ora il codice per il primo metodo di ottimizzazione ( cioè controllando fino a √n )

la sottostringa Java contiene

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('Vero' ) else: print('False') else: print('False')>

False>

Complessità temporale :O(quadrato(n))
Spazio ausiliario: O(1)

Controllare i numeri primi utilizzando la ricorsione

Possiamo anche trovare il numero primo o non usarlo ricorsione . Possiamo utilizzare la logica esatta mostrata nel metodo 2 ma in modo ricorsivo.

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>

Complessità temporale: O(quadrato(n))
Spazio ausiliario :O(quadrato(n))

Controlla il metodo 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>

Complessità temporale: O(sqrt(n))
Spazio ausiliario: O(sqrt(n))

Articolo consigliato – Analisi di diversi metodi per trovare i numeri primi in Python

Programma Python per verificare i numeri primi Utilizzando un ciclo while per verificare la divisibilità

Inizializza una variabile da i a 2, mentre i al quadrato è minore o uguale a n, controlla se n è divisibile per i. Se n è divisibile per i, restituisce False. Altrimenti, incrementa i di 1. Se il ciclo termina senza trovare un divisore, restituisce 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>

Complessità temporale: O(sqrt(n))
Spazio ausiliario: O(1)

Programma Python per controllare i numeri primi utilizzando il modulo matematico

Il codice implementa un approccio di base per verificare se un numero è primo o meno, attraversando tutti i numeri da 2 a sqrt(n)+1 e controllando se n è divisibile per uno qualsiasi di questi numeri.

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>

Complessità temporale: O(quadrato(n))
La complessità temporale del codice è O(sqrt(n)) perché attraversiamo tutti i numeri nell'intervallo da 2 a sqrt(n)+1 per verificare se n è divisibile per qualcuno di essi.

Spazio ausiliario: O(1)
La complessità spaziale del codice è O(1) poiché utilizziamo solo una quantità costante di memoria per memorizzare il numero di input n e le variabili del ciclo.

Programma Python per controllare il numero primo utilizzando il metodo sympy.isprime()

Nel modulo sympy, possiamo verificare se un dato numero n è primo o meno utilizzando la funzione sympy.isprime(). Per n <2⁶⁴la risposta è definitiva; valori n più grandi hanno una piccola probabilità di essere effettivamente pseudoprimi.

N.B.: I numeri negativi (ad esempio -13) non sono considerati numeri primi.

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

Produzione

False True True>

Complessità temporale: O(sqrt(n)), dove n è il numero di input.
Spazio ausiliario: O(1)