Kuriosa om en snabb primtalsberäkning

Primtal. Vem kan inte älska dem? De är matematikens särlingar och ändå så användbara.
Utan primtal skulle vi inte kunna kryptera känslig information.

I mars i år deltog jag i en uppmaning att skriva kod så att korrekta primtal upp till 10 000 skulle produceras så fort som möjligt. Jag visste att jag hade en bra chans då jag ganska nyligen deltagit i Celkos tävling (http://www.sqlservercentral.com/articles/T-SQL/67666/) om precis samma uppgift. Men istället för att bara posta samma lösning (http://www.sqlservercentral.com/Forums/Topic759697-1604-1.aspx) igen så ville jag tänka igenom uppgiften om det fanns en annan algoritm som var snabbare än den jag kom tvåa med.

Jag började med att rita upp alla tal upp till 120 på ett papper.

image

Jag segmenterade talen om 30, då de tre första primtalen 2, 3, och 5 har en produkt som blir 30. Detta gjorde jag eftersom att efter 30 så skulle mönstret upprepa sig. Detta är en viktig insikt, att mönstret kommer att upprepa sig.

Som ni kan se i bilden ovan, markerar de röda blocken de tal som omöjligen är ett primtal då de är delbara med antingen 2, 3, eller 5. Kvar är de gröna eller blå talen som är möjliga primtal. Som du kan se finns det som mest 8 möjliga primtal i varje segment. I realiteten finns det bara sju primtal då ett av de möjliga primtalen är falskt.
1 är per definition inte ett primtal, 47 är produkten av sju och sju, 77 är produkten av sju och elva, 91 är produkten av sju och tretton samt 119 som är produkten av sju och sjutton. Denna insikt innebär att jag bara behöver testa 8 av 30 tal i varje segment dvs 26.67% av talen, en avsevärd prestandaförbättring!

Jag bestämde mig för att det skulle räcka med att producera ett visst antal segment upp till det önskade primtalet. Dessutom behöver jag inte kontrollera 2, 3 och 5 då dessa redan har använts för att bestämma segmentets storlek, benämnt x. Det första tal jag behöver kontrollera är 7, dvs x – 23. De följande talen blir 11 (x – 19), 13 (x – 17), 17 (x – 13), 19 (x- 11), 23 (x – 7) samt 29 (x – 1). Men eftersom jag jag skjutit på sekvensserien med sju steg så måste jag även ta med 31 (x + 1). Då har jag mina åtta primtalskandidater och dessa sparar jag i en temporär tabell. Om jag nu ska visa alla primtal upp till 1 000 000 så behöver jag bara lagra 266 665 tal.

Nu när jag har mina primtalskandidater så behöver jag bara kontrollera om det för varje primtalskandidat finns ett lägre tal som ingår i primtalskandidatens faktorisering. Och det är känt sedan tidigare att man bara behöver testa faktorisering upp till roten av primtalskandidaten.

Nu började koden ta form. Jag skulle producera lika många 30-talssegment upp till det önskade primtalet och bara de möjliga kandidaterna. Sedan skulle jag kontrollera för alla primtalskandidater om det finns ett lägre tal (upp till roten av primtalskandidaten) som ingår i faktoriseringen av primtalskandidaten.

Så här blev det till slut.

CREATE TABLE    #Numbers
                (
                        PrimeCandidate INT NOT NULL,
                        PrimalityTest BIGINT PRIMARY KEY CLUSTERED
                );

DECLARE @MaxPrime BIGINT = 1000000;

WITH n0(p)
AS (
        SELECT  1 UNION ALL
        SELECT  1
), n1(p)
AS (
        SELECT          1
        FROM            n0 AS a
        CROSS JOIN      n0 AS b
), n2(p)
AS (
        SELECT          1
        FROM            n1 AS a
        CROSS JOIN      n1 AS b
), n3(p)
AS (
        SELECT          1
        FROM            n2 AS a
        CROSS JOIN      n2 AS b

), n4(p)
AS (
        SELECT          1
        FROM            n3 AS a
        CROSS JOIN      n3 AS b
), n5(p)
AS (
        SELECT          1
        FROM            n4 AS a
        CROSS JOIN      n4 AS b
)
INSERT          #Numbers
                (
                        PrimeCandidate,
                        PrimalityTest
                )
SELECT          f.PrimeCandidate,
                f.PrimeCandidate * f.PrimeCandidate AS PrimalityTest
FROM            (
                        SELECT  TOP (1 + @MaxPrime / 30)
                                30 * ROW_NUMBER() OVER (ORDER BY p) AS Segment
                        FROM    n5
                ) AS v(Segment)
CROSS APPLY     (
                        VALUES  (v.Segment 23),
                                (v.Segment 19),
                                (v.Segment 17),
                                (v.Segment 13),
                                (v.Segment 11),
                                (v.Segment   7),
                                (v.Segment   1),
                                (v.Segment +  1)
                ) AS f(PrimeCandidate)
WHERE           f.PrimeCandidate <= @MaxPrime;

SELECT  Prime
FROM    (
                VALUES  (2),
                        (3),
                        (5)
        ) AS v(Prime)
WHERE   Prime <= @MaxPrime

UNION ALL

SELECT  n.PrimeCandidate AS Prime
FROM    #Numbers AS n
WHERE   NOT EXISTS      (
                                SELECT  *
                                FROM    #Numbers AS p
                                WHERE   p.PrimalityTest <= n.PrimeCandidate
                                        AND n.PrimeCandidate % p.PrimeCandidate = 0
                        );

DROP TABLE      #Numbers;

Denna kod producerar alla primtal (78 498) upp till 1 000 000 på cirka 1,5 sekund på min laptop. Jag har provat med att använda 7 som basprimtal med, för att utöka segmentstorleken till 210 men det verkar som de 48 primtalskandidaterna i dessa segment (22,86%) inte ger så stor förbättring.

CREATE TABLE    #Numbers
                (
                        PrimeCandidate INT NOT NULL,
                        PrimalityTest BIGINT PRIMARY KEY CLUSTERED
                );

DECLARE @MaxPrime BIGINT = 1000000;

WITH n0(p)
AS (
        SELECT  1 UNION ALL
        SELECT  1
), n1(p)
AS (
        SELECT          1
        FROM            n0 AS a
        CROSS JOIN      n0 AS b
), n2(p)
AS (
        SELECT          1
        FROM            n1 AS a
        CROSS JOIN      n1 AS b
), n3(p)
AS (
        SELECT          1
        FROM            n2 AS a
        CROSS JOIN      n2 AS b

), n4(p)
AS (
        SELECT          1
        FROM            n3 AS a
        CROSS JOIN      n3 AS b
), n5(p)
AS (
        SELECT          1
        FROM            n4 AS a
        CROSS JOIN      n4 AS b
)
INSERT          #Numbers
                (
                        PrimeCandidate,
                        PrimalityTest
                )
SELECT          f.PrimeCandidate,
                f.PrimeCandidate * f.PrimeCandidate AS PrimalityTest
FROM            (
                        SELECT  TOP (1 + @MaxPrime / 210)
                                210 * ROW_NUMBER() OVER (ORDER BY p) AS Segment
                        FROM    n5
 
              ) AS v(Segment)
CROSS APPLY     (
                        VALUES  (v.Segment 199),
                                (v.Segment 197),
                                (v.Segment 193),
                                (v.Segment 191),
                                (v.Segment 187),
                                (v.Segment 181),
                                (v.Segment 179),
                                (v.Segment 173),
                                (v.Segment 169),
                                (v.Segment 167),
                                (v.Segment 163),
                                (v.Segment 157),
                                (v.Segment 151),
                                (v.Segment 149),
                                (v.Segment 143),
                                (v.Segment 139),
                                (v.Segment 137),
                                (v.Segment 131),
                                (v.Segment 127),
                                (v.Segment 121),
                                (v.Segment 113),
                                (v.Segment 109),
                                (v.Segment 107),
                                (v.Segment 103),
                                (v.Segment 101),
                                (v.Segment   97),
                                (v.Segment   89),
                                (v.Segment   83),
                                (v.Segment   79),
                                (v.Segment   73),
                                (v.Segment   71),
                                (v.Segment   67),
                                (v.Segment   61),
                                (v.Segment   59),
                                (v.Segment   53),
                                (v.Segment   47),
                                (v.Segment   43),
                                (v.Segment   41),
                                (v.Segment   37),
                                (v.Segment   31),
                                (v.Segment   29),
                                (v.Segment   23),
                                (v.Segment   19),
                                (v.Segment   17),
                                (v.Segment   13),
                                (v.Segment   11),
                                (v.Segment    1),
                                (v.Segment +   1)
                ) AS f(PrimeCandidate)
WHERE           f.PrimeCandidate <= @MaxPrime;

SELECT  Prime
FROM    (
                VALUES  (2),
                        (3),
                        (5),
                        (7)
        ) AS v(Prime)
WHERE   Prime <= @MaxPrime

UNION ALL

SELECT  n.PrimeCandidate AS Prime
FROM    #Numbers AS n
WHERE   NOT EXISTS      (
                                SELECT  *
                                FROM    #Numbers AS p
                                WHERE   p.PrimalityTest <= n.PrimeCandidate
                                        AND n.PrimeCandidate % p.PrimeCandidate = 0

                        );

DROP TABLE      #Numbers;

Leave a Reply