Controle over een getal priem is in Python

Deze tutorial leert je hoe je een Python-programma schrijft om te controleren of een getal priem is van niet.

Als je ooit coderingstoetsen hebt gedaan, ben je vast de wiskundige vraag tegengekomen over de test voor primaliteit of om te controleren of een getal priem is. In de volgende paar minuten leer je hoe je de optimale oplossing voor deze vraag kunt vinden.

In deze zelfstudiegids zul je:

• de basisprincipes van priemgetallen doornemen,
• python-code schrijven om te controleren of een getal priem is, en
• deze verder optimaliseren om een O(√n) runtime algoritme te krijgen.

Laten we voor dit alles en meer aan de slag gaan.

Wat is een priemgetal?

Laten we beginnen met de basisprincipes van priemgetallen.

In de getaltheorie is een natuurlijk getal n een priemgetal als het precies twee factoren heeft: 1 en het getal zelf(n). Weet je nog van wiskunde op school: van een getal i wordt gezegd dat het een factor is van het getal nals i n evenredig deelt. ✅

De volgende tabel toont een aantal getallen, al hun factoren en of ze priem zijn.

Uit bovenstaande tabel kunnen we de volgende opschrijven:

• 2 is het kleinste priemgetal.
• 1 is een factor van elk getal.
• Eland getal n is een factor van zichzelf.

Dus 1 en n zijn triviale factoren voor elk getal n. En een priemgetal mag geen andere factoren hebben dan deze twee.

Dit betekent dat als je van 2 naar n - 1 gaat, je geen niet-triviale factor zou moeten kunnen vinden die n deelt zonder rest.

O(n) algoritme om een getal priem te controleren is in Python

Laten we in dit gedeelte de bovenstaande aanpak formaliseren in een Python-functie.

Je kunt door alle getallen van 2 tot n - 1 lussen met behulp van het object bereik() in Python.

In Python geeft bereik(start, stop, stap) een bereikobject terug. Je kunt dan itereren over het bereikobject om een reeks te krijgen van start helemaal tot stop -1 in stappen van stap.

Omdat we de reeks gehele getallen van 2 tot n-1 nodig hebben, kunnen we range(2, n) specificeren en het gebruiken in combinatie met de for-lus.

Dit is wat we willen doen:

• Als je een getal vindt dat n gelijkmatig deelt zonder rest, kun je meteen concluderen dat het getal niet priem is.

• Als je door het hele bereik van getallen van 2 tot n - 1 bent gelopen zonder een getal te vinden dat n gelijkmatig deelt, dan is het getal priem.

Python Functie om op priemgetal te controleren

Met behulp van het bovenstaande kunnen we verder gaan en de functie is_prime() als volgt definiëren.

def is_prime(n):
 voor i in range(2,n):
 als (n%i) == 0:
 return False
 return True

Laten we nu de bovenstaande functiedefinitie ontleden.

• De bovenstaande functie is_prime() neemt een positief geheel getal n als argument.
• Als je een factor vindt binnen het gespecificeerde bereik van (2, n-1), retourneert de functie False-omdathet getal niet priem is.
• En de functie geeft True terug als je de hele lus doorloopt zonder een factor te vinden.

Laten we vervolgens de functie met argumenten aanroepen en controleren of de uitvoer juist is.

is_prime(2)
# True

is_prime(8)
# False

is_prime(9)
# False

is_prime(11)
# True

In de bovenstaande uitvoer zie je dat 2 en 11 priem zijn (de functie geeft True). En 8 en 9 zijn niet priem (de functie geeft Vals).

De Python-functie is_prime() optimaliseren

We kunnen hier een kleine optimalisatie doen. Kijk naar de lijst met factoren in de tabel hieronder.

We zien dat de enige factor van n die groter is dan n/2 n zelf is.

Dit betekent dus dat je niet helemaal door hoeft te lussen tot n - 1. In plaats daarvan kun je de lus tot n/2 laten lopen.

Als je geen niet-triviale factor vindt tot n/2, kun je er ook geen voorbij n/2 vinden.

Laten we nu de functie is_prime() aanpassen om te controleren op factoren in het bereik (2, n/2)

def is_prime(n):
 voor i in bereik(2,int(n/2)):
 als (n%i) == 0:
 return False
 return True

Laten we doorgaan en de uitvoer verifiëren met een paar functieaanroepen.

is_prime(9)
# False

is_prime(11)
# True

Hoewel het lijkt alsof we geoptimaliseerd hebben, is dit algoritme niet efficiënter dan het vorige in termen van runtime complexiteit. In feite hebben ze beide O(n) runtime complexiteit: evenredig met de waarde van n of lineair in n.

Kunnen we het beter doen? Ja, dat kunnen we!

▶️ Ga verder naar de volgende sectie om te bepalen hoe we de tijdcomplexiteit voor het testen van priemgetallen kunnen verbeteren.

O(√n) algoritme om te controleren op priemgetallen in Python

Het komt voor dat de factoren van een getal in paren voorkomen.

Als a een factor is van het getal ndan bestaat er ook een factor b zodat a x b = nvan simpelweg, ab = n.

Laten we dit verifiëren aan de hand van een voorbeeld.

De tabel hieronder toont de factoren van het getal 18 die paarsgewijs voorkomen. Als je wilt, kun je hetzelfde doen voor nog een paar getallen.

Merk ook op dat √18 ongeveer 4,24 is.

En in de factoren die voorkomen in paren (a, b), kun je zien dat als a kleiner is dan 4,24, b groter is dan 4,24 - in dit voorbeeld (2, 18) en (3, 6).

De figuur hieronder toont de factoren van 18 uitgezet op de getallenlijn.

Als het getal n toevallig een perfect kwadraat is, dan heb je a = b = √n als een van de factoren.

▶️ Bekijk de factoren van 36 in de tabel hieronder. Omdat 36 een perfecte kwadraat is, is a = b = 6 een van de factoren. Voor alle andere factorparen (a, b) geldt a 6.

Samenvattend hebben we het volgende:

• Eland getal n kan worden geschreven als n = a x b
• Als n een perfecte kwadraat is, dan is a = b = √n.
• En als a < bdan is a < √n en b > √n.
• Anders, als a > bdan a > √n en b < √n.

Dus in plaats van door alle gehele getallen tot n/2 te lopen, kun je ervoor kiezen om tot √n te lopen. En dit is een stuk efficiënter dan onze vorige aanpak.

Hoe is_prime() wijzigen in O(√n) algoritme

Laten we verder gaan met het optimaliseren van de functie om te controleren op priemgetallen in Python.

importeer wiskunde
def is_prime(n):
 for i in range(2,int(math.sqrt(n)) 1):
 if (n%i) == 0:
 return False
 return True

Laten we nu de bovenstaande functiedefinitie ontleden:

• Om de vierkantswortel van een getal te berekenen, importeren we de ingebouwde wiskunde-module van Python en gebruiken we de functie math.sqrt().
• Omdat n misschien geen perfecte vierkant is, moeten we het omzetten in een geheel getal. Gebruik int(var) om var om in een int.
• Om er zeker van te zijn dat we daadwerkelijk tot √n controleren, voegen we een plus één toe omdat de bereik() functie standaard het eindpunt van het bereik uitsluit.

De codecel hieronder controleert of onze functie is_prime() correct werkt.

is_prime(8)
# False

is_prime(15)
# False

is_prime(23)
# True

Laten we in de volgende sectie een paar eenvoudige plots maken om O(n) en O(√n) visueel te begrijpen.

O(n) en O(√n) visueel vergelijken

▶️ Voer het volgende codefragment uit in een Jupyter notitieblok-omgeving naar keuze.

importeer numpy als np
importeer seaborn als sns
importeer pandas als pd


n = 20

x = np.arange(n)
y1 = np.sqrt(x)
y2 = x
df = pd.DataFrame({"O(√n)":y1,"O(n)":y2})
sns.set_thema()
sns.lineplot(data = df)

Het bovenstaande fragment laat zien hoe je de curven voor n en √n kunt plotten voor een reeks waarden.

• We gebruiken de functie NumPy arange() om een array van getallen te maken.
• Vervolgens verzamelen we de waarden van n en √n tot en met 20 in een pandas gegevensframe.
• Vervolgens plotten we de functie lijndiagram() van zeeborn.

In de plot hieronder zien we dat √n aanzienlijk kleiner is dan n.

Laten we nu het bereik vergroten tot 2000 en dezelfde stappen als hierboven herhalen.

import numpy as np
import seaborn as sns
import pandas as pd


n = 2000

x = np.arange(n)
y1 = np.sqrt(x)
y2 = x
df = pd.DataFrame({"O(√n)":y1,"O(n)":y2})
sns.set_thema()
sns.lineplot(data = df)

Uit de bovenstaande grafiek kun je afleiden dat het O(√n) algoritme aanzienlijk sneller is als je test of een groot getal priem is.

Hier is een snel voorbeeld: 2377 is een priemgetal - controleer dit!

Terwijl de O(n) benadering 2000 stappen in beslag neemt, kan het O(√n) algoritme helpen om in slechts 49 stappen tot het antwoord te komen.✅

Conclusie

⏳ En het is tijd voor een korte samenvatting.

• Om te controleren of een getal priem is, is de naïeve benadering om door alle getallen in het bereik (2, n-1) te lopen. Als je geen factor vindt die n deelt, dan is n priem.
• Omdat de enige factor van n groter dan n/2 n zelf is, kun je ervoor kiezen om alleen tot n/2 te lopen.
• Beide bovenstaande benaderingen hebben een tijdscomplexiteit van O(n).
• Omdat factoren van een getal paarsgewijs voorkomen, kun je slechts tot √n uitvoeren. Dit algoritme is veel sneller dan O(n). En de winst is aanzienlijk bij het controleren of een groot getal priem is of niet.

Ik hoop dat je begrijpt hoe je kunt controleren of een getal priem is in Python. Als volgende stap kun je onze tutorial over Python-programma's voor tekenreeksbewerkingenbekijken waarinje leert om te controleren of tekenreeksen palindromen, anagrammen en meer zijn.

Tot ziens in een volgende tutorial. Tot dan, veel plezier met coderen! 👩🏽‍💻