Controlla se un numero è primo in Python

Un numero primo può essere rappresentato come un numero naturale senza altri divisori positivi, ad eccezione del numero 1 e di se stesso. Il numero 1 non viene conteggiato nella lista dei numeri primi.

Questo tutorial discuterà i diversi metodi che puoi usare per verificare se un numero è un numero primo.

Usa il metodo di iterazione semplice per determinare un numero primo in Python

In questo metodo, utilizziamo un semplice metodo di iterazione utilizzando un cicli for o while. Iterare attraverso i numeri a partire da 2 e salendo fino a K/2 e verificando se uno di questi numeri divide K.

Se viene trovato un numero che corrisponde a questo criterio, viene restituito False. D’altra parte, se tutti i numeri non soddisfano questo criterio, il numero K dato è un numero primo e viene restituito il valore True.

Il codice seguente usa il metodo di iterazione semplice per verificare se il numero dato è un numero primo in Python.

k = 13

# 1 not being a prime number, is ignored
if k > 1:
    for i in range(2, int(k / 2) + 1):
        if (k % i) == 0:
            print("It is not a prime number")
            break
    else:
        print("It is a prime number")

else:
    print("It is not a prime number")

Produzione:

It is a prime number

Puoi ottimizzare il codice sopra applicando alcune modifiche. Effettua le seguenti ottimizzazioni per rendere il codice ancora più veloce:

*Controllare fino a raggiungere la radice del numero dato invece di controllare il numero esatto. Questo processo elimina sostanzialmente la ridondanza che si verifica quando un fattore più grande del numero K è un multiplo di un fattore più piccolo che è già stato ripetuto.

*Tutti i numeri primi esistono nella forma di 6n±1, con 2 e 3 come uniche eccezioni. Pertanto, controllare la divisibilità del numero dato con 2 e 3, e quindi controllare ogni numero che ha la forma 6n±1 è la soluzione più efficiente.

Il codice seguente usa il metodo di iterazione semplice ottimizzato per verificare se il numero dato è un numero primo in Python.

def isitPrime(k):
    if k == 2 or k == 3:
        return True
    if k % 2 == 0 or k < 2:
        return False
    for i in range(3, int(k ** 0.5) + 1, 2):
        if k % i == 0:
            return False

    return True


print(isitPrime(13))

Produzione:

True

Il metodo di iterazione ottimizzato lo rende più veloce ed efficiente di circa il 30% rispetto al metodo di iterazione semplice.

Usa la funzione sympy.isprime() per verificare se il numero dato è un numero primo in Python

SymPy è una libreria in Python utilizzata per implementare la matematica simbolica. Vuole essere un sistema di computer algebra (CAS) semplicistico che contenga tutte le caratteristiche essenziali. L’installazione di questo modulo è necessaria per questo metodo e può essere scaricato semplicemente usando il comando pip.

La funzione sympy.isprime() è una funzione integrata nel modulo SymPy e può essere utilizzata per verificare eventuali numeri primi. È una funzione diretta e restituisce True se il numero da controllare è primo e False se il numero non è primo.

Il codice seguente usa la funzione sympy.isprime() per verificare se il numero dato è un numero primo in Python.

from sympy import *

isprime(8)
isprime(11)

Produzione:

False
True

Dobbiamo notare che qualsiasi numero negativo non rientra nei criteri dei Numeri Primi. L’output di queste funzioni può variare se viene confrontato un numero negativo.