Primtal¶

Primtal är en av de fundamentala byggstenarna inom de område som heter talteori i Matematiken. Egenskapern har i och med introduktionen av datorerna från sent 1900-tal och framåt fått ett rejält uppsving. Primtalen används i allt från prestandatestning till kanske den viktigaste tilläpningen där de används till kryptering mellan sändare och mottagare på internet.

Men låt oss börja med en defintion.

Definition: Primtal är ett positivt heltal som endast är delbart med sig själv och talet ett.

Test om ett tal är ett heltal eller inte. Det enklaste testet som går att gör är att kontrollera om talet är delbart med något av alla tal som är mindre än talet. I python kan koden exempelvis se ut som:

def PrimtalsTest(n):
    for i in range(n):
        if (n % i == 0):
            print(i)

Algoritmen ovanför testar om ett givet tal n får en rest vid division med talet i. I så fall skrivs talet i ut. Vid test av talet 16 kan en körning se ut som nedan.

In [106]:

%%timeit
#%save file

def primtalsTest1(n):
    for i in range(2,n):
        if (n % i == 0):
            #print(i)
            return False
    return True


#kör funktionen för alla taö mellan 2 och 50 000
for n in range(2,5000):
    #print(n, primtalsTest1(n))
    primtalsTest1(n)

270 ms ± 2.52 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Algoritmen ovanför är relativt ineffektiv. Den kan göras snabbare genom att göra smarta val för vilka tal som testas. Exempelvis

testa inte jämna tal. Det enda jämna tal som är ett primtal är 2.
testa inte alla tal som är mindre än talet. Det räcker att gå till roten ur talet
test bara udda tal.

En algoritm som implementerar detta kan se ut som följande.

In [107]:

%%timeit

import math

def primtalsTest2(n):
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    n_root = math.ceil(math.sqrt(n))
    
    for i in range(3,n_root,2):
        if (n % i == 0):
            return False
    return True

for n in range(2,5000):
    #print(n, primtalsTest2(n))
    primtalsTest2(n)

11.4 ms ± 603 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

Det finns några ytterligare förbättringar man kan göra för att snabba upp algoritmen ytterligare. [1]

I nästa artikel ska vi använda denn algoritm för att hitta delare till ett tal, resten av denna artikel kommer att ägnas åt distributionen av primtal. Styrkan med datorer är deras överlägsna beräkningshastighet så låt oss använda den för att undersöka hur primtalen fördelar sig.

Tänk en funktion $\Pi(n)$ som ger antalet primtal mindre än talet $n$. Gör vi det för de 100 första heltalen så erhålls följande tabell.

$n$	$\Pi$
10	4
50	15
100	25

En funktion som löser detta problem kan se ut som följande. Vi plottar upp funktionen för lite större datamängder och undersöker hur de ser ut.

[1]: Primality Tests

In [105]:

import matplotlib.pyplot as py
%matplotlib inline

def primeCounter(n):
    sum = 0
    for n in range(2, n+1):
        if primtalsTest2(n):
            sum += 1
    return sum

xs = [10*x for x in range(1, 100)]
ys = [primeCounter(10*x) for x in range(1,100)]

py.plot(xs, ys)

Out[105]:

[<matplotlib.lines.Line2D at 0x27c156089b0>]

Slut på artikeln.

//SoS

Startsidan