Denne vejledning vil lære dig, hvordan du skriver et Python-program for at kontrollere, om et tal er primtal eller ej.
Hvis du nogensinde har taget kodningsprøver, vil du være stødt på matematikspørgsmålet på testen for primært eller for at kontrollere, om et tal er primtal. Og i løbet af de næste par minutter lærer du at komme med den optimale løsning på dette spørgsmål.
I dette selvstudie skal du:
- gennemgå det grundlæggende i primtal,
- skriv Python-kode for at kontrollere, om et tal er primtal, og
- optimer det yderligere for at få en O(√n) runtime-algoritme.
For alt dette og mere, lad os komme i gang.
Indholdsfortegnelse
Hvad er et primtal?
Lad os starte med at gennemgå det grundlæggende i primtal.
I talteorien siges et naturligt tal n at være prime hvis det har præcis to faktorer: 1 og selve tallet (n). Husk fra din skolematematik: et tal i siges at være en faktor af tallet n, hvis i deler n ligeligt. ✅
Den følgende tabel viser nogle få tal, alle deres faktorer, og hvis de er primtal.
nFactorsIs Prime?11Nej21, 2Ja31, 3Ja41, 2, 4Nej71, 7Ja151, 3, 5, 15Nej
Fra ovenstående tabel kan vi skrive følgende ned:
- 2 er det mindste primtal.
- 1 er en faktor af hvert tal.
- Hvert tal n er en faktor i sig selv.
Så 1 og n er trivielle faktorer for ethvert tal n. Og et primtal bør ikke have andre faktorer end disse to.
Det betyder, at når man går fra 2 til n – 1, skal man ikke kunne finde en ikke-triviel faktor, der deler n uden en rest.
O(n) Algoritme til at kontrollere, om et tal er primtal i Python
Lad os i dette afsnit formalisere ovenstående tilgang til en Python-funktion.
Du kan sløjfe gennem alle tal fra 2 til n – 1 ved at bruge range()-objektet i Python.
I Python returnerer range(start, stop, step) et områdeobjekt. Du kan derefter iterere over områdeobjektet for at få en sekvens fra start og helt op til stop -1 i trin af trin.
Da vi har brug for sættet af heltal fra 2 til n-1, kan vi angive range(2, n) og bruge det sammen med for loop.
Her er, hvad vi gerne vil gøre:
- Hvis du finder et tal, der deler n ligeligt uden en rest, kan du med det samme konkludere, at tallet ikke er primtal.
- Hvis du har sløjfet hele rækken af tal fra 2 helt op til n – 1 uden at finde et tal, der deler n ligeligt, så er tallet primtal.
Python-funktion til at tjekke for primtal
Ved at bruge ovenstående kan vi gå videre og definere funktionen is_prime() som følger.
def is_prime(n):
for i in range(2,n):
if (n%i) == 0:
return False
return True
Lad os nu analysere ovenstående funktionsdefinition.
- Ovenstående funktion is_prime() tager et positivt heltal n som argument.
- Hvis du finder en faktor i det angivne interval (2, n-1), returnerer funktionen Falsk – da tallet ikke er primtal.
- Og det returnerer True, hvis du krydser hele løkken uden at finde en faktor.
Lad os derefter kalde funktionen med argumenter og kontrollere, om outputtet er korrekt.
is_prime(2) # True is_prime(8) # False is_prime(9) # False is_prime(11) # True
I outputtet ovenfor ser du, at 2 og 11 er prime (funktionen returnerer Sand). Og 8 og 9 er ikke primtal (funktionen returnerer Falsk).
Sådan optimeres Python-funktionen is_prime()
Vi kan lave en lille optimering her. Overhold listen over faktorer i nedenstående tabel.
NumberFactors61, 2, 3, 6101, 2, 5, 10181, 2, 3, 6, 9, 18
Nå, vi kan se, at den eneste faktor af n, der er større end n/2, er n selv.
Så det betyder, at du ikke behøver at sløjfe helt op til n – 1. Du kan i stedet kun køre løkken op til n/2.
Hvis du ikke finder en ikke-triviel faktor indtil n/2, kan du heller ikke finde en ud over n/2.
Lad os nu ændre funktionen is_prime() for at tjekke for faktorer i området (2, n/2)
def is_prime(n):
for i in range(2,int(n/2)):
if (n%i) == 0:
return False
return True
Lad os gå videre og verificere outputtet gennem et par funktionskald.
is_prime(9) # False is_prime(11) # True
Selvom det kan virke som om, vi har optimeret, er denne algoritme ikke mere effektiv end den forrige med hensyn til runtime-kompleksitet. Faktisk har de begge O(n) runtime kompleksitet: proportional med værdien af n eller lineær i n.
Kan vi gøre det bedre? Ja vi kan!
▶️ Fortsæt til næste afsnit for at bestemme, hvordan man kan forbedre tidskompleksiteten for primtalstestning.
O(√n) Algoritme til at tjekke for primtal i Python
Det sker, at faktorerne i et tal optræder i par.
Hvis a er en faktor af tallet n, så eksisterer der også en faktor b, således at axb = n, eller simpelthen ab = n.
Lad os bekræfte dette gennem et eksempel.
Tabellen nedenfor viser faktorerne for tallet 18, der forekommer i par. Du kan bekræfte det samme for et par flere numre, hvis du vil.
Bemærk også, at √18 er cirka 4,24.
Og i de faktorer, der forekommer i par (a, b), kan du se, at hvis a er mindre end 4,24, så er b større end 4,24 – i dette eksempel (2, 18) og (3, 6).
Faktorer på 18 i par
Nedenstående figur viser faktorerne 18 plottet på tallinjen.
Hvis tallet n tilfældigvis er et perfekt kvadrat, vil du have a = b = √n som en af faktorerne.
▶️ Se på faktorerne 36 i tabellen nedenfor. Da 36 er et perfekt kvadrat, er a = b = 6 en af faktorerne. For alle andre faktorpar (a, b) gælder a < 6 og b > 6.
Faktorer på 36 i par
Sammenfattende har vi følgende:
- Hvert tal n kan skrives som n = axb
- Hvis n er et perfekt kvadrat, så er a = b = √n.
- Og hvis a < b, så a < √n og b > √n.
- Ellers, hvis a > b, så a > √n og b < √n.
Så i stedet for at gå gennem alle heltal op til n/2, kan du vælge at løbe op til √n. Og dette er meget mere effektivt end vores tidligere tilgang.
Sådan ændres is_prime() til O(√n) algoritme
Lad os fortsætte med at optimere funktionen for at tjekke for primtal i Python.
import math
def is_prime(n):
for i in range(2,int(math.sqrt(n))+1):
if (n%i) == 0:
return False
return True
Lad os nu analysere ovenstående funktionsdefinition:
- For at beregne kvadratroden af et tal, lad os importere Pythons indbyggede matematikmodul og bruge math.sqrt()-funktionen.
- Da n måske ikke er et perfekt kvadrat, bliver vi nødt til at støbe det ind i et heltal. Brug int(var) til at kaste var ind i en int.
- For at sikre, at vi rent faktisk tjekker op til √n, tilføjer vi et plus et, da range()-funktionen som standard ekskluderer endepunktet for området.
Kodecellen nedenfor bekræfter, at vores funktion is_prime() fungerer korrekt.
is_prime(8) # False is_prime(15) # False is_prime(23) # True
Lad os i næste afsnit lave et par simple plots for at forstå O(n) og O(√n) visuelt.
Sammenligning af O(n) og O(√n) visuelt
▶️ Kør følgende kodestykke i et Jupyter notebook-miljø efter eget valg.
import numpy as np
import seaborn as sns
import pandas as pd
n = 20
x = np.arange(n)
y1 = np.sqrt(x)
y2 = x
df = pd.DataFrame({"O(√n)":y1,"O(n)":y2})
sns.set_theme()
sns.lineplot(data = df)
Ovenstående uddrag viser, hvordan du kan plotte kurverne for n og √n for en række værdier.
- Vi bruger funktionen NumPy arange() til at skabe en matrix af tal.
- Og så samler vi værdierne af n og √n op til, men ikke inklusive 20, i en pandas DataFrame.
- Dernæst plotter vi vha seaborns lineplot() fungere.
Fra plottet nedenfor ser vi, at √n er væsentligt mindre end n.
Lad os nu øge området til så højt som 2000 og gentage de samme trin som ovenfor.
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_theme()
sns.lineplot(data = df)
Fra ovenstående plot kan du udlede, at O(√n)-algoritmen er betydeligt hurtigere, når du tester, om et stort tal er primtal.
Her er et hurtigt eksempel: 2377 er et primtal – bekræft dette!😀
Mens O(n)-tilgangen vil tage størrelsesordenen 2000 trin, kan O(√n)-algoritmen hjælpe med at nå frem til svaret på kun 49 trin.✅
Konklusion
⏳ Og det er tid til en hurtig opsummering.
- For at kontrollere, om et tal er primtal, er den naive tilgang at gå gennem alle tal i området (2, n-1). Hvis du ikke finder en faktor, der deler n, så er n primtal.
- Da den eneste faktor på n større end n/2 er n selv, kan du vælge kun at køre op til n/2.
- Begge de ovennævnte tilgange har en tidskompleksitet på O(n).
- Da faktorer af et tal forekommer i par, kan du kun køre op til √n. Denne algoritme er meget hurtigere end O(n). Og gevinsten er mærkbar, når man kontrollerer, om et stort tal er prime eller ej.
Jeg håber, du forstår, hvordan du tjekker, om et tal er primtal i Python. Som et næste trin kan du tjekke vores tutorial om Python-programmer om strengoperationer – hvor du lærer at kontrollere, om strenge er palindromer, anagrammer og mere.
Vi ses i en anden tutorial. Indtil da, glædelig kodning!👩🏽💻