matematikk.net

Lagt inn: **07/04-2018 20:22**

Gjennom noen Project Euler-oppgaver blir man nødt til å avgjøre om enkelte enorme tall er primtall.

En kjapp og naiv sjekk er å prøve å dividere tallet $n$ med alle tall $2\ldots n-1$, som deretter kan videre forbedres ved å gjøre enkelte observasjoner, som at man ikke trenger å sjekke lengre enn til $\sqrt n$ og man trenger kun å sjekke oddetall etter $2$. Så divisjon med $2, 3, 5, 7, \ldots, \sqrt{n-1}$.

Men jeg merker at til tross for at man her kun tester ett tall, så er det enda kjappere å bruke Eratosthenes' sil. Kjappere, men med større minnebruk.

https://no.wikipedia.org/wiki/Eratosthenes%27_sil

Er det noen som er kjent med enda raskere sjekker? Eventuelt forbedringer på den naive fremgangsmåten?

Lagt inn: **08/04-2018 00:29**

https://en.wikipedia.org/wiki/AKS_primality_test

Edit: Virker som AKS ikke er en god metode i praksis. En modifisert versjon AKS, av Lenstra og Pomerance, skal visst være rask: https://www.math.dartmouth.edu/~carlp/P ... xity12.pdf . Ellers virker det som probabilistiske tester er raske, som Miller-Rabin og Baillie-PSW https://en.wikipedia.org/wiki/Baillie%E ... ality_test, for å vise at tall er sammensatte.

Lagt inn: **09/04-2018 00:30**

Jeg har ikke et svar, men jeg lurte på hvorfor man ikke trenger å sjekke lengre enn til [tex]\sqrt{n}[/tex] ?

Lagt inn: **09/04-2018 01:02**

Leonhard_Euler skrev:Jeg har ikke et svar, men jeg lurte på hvorfor man ikke trenger å sjekke lengre enn til [tex]\sqrt{n}[/tex] ?

Kort sagt:

Vi vet at $n = \sqrt n \cdot \sqrt n$.

Derfor vet vi også at dersom det finnes en primfaktor $ p_1 > \sqrt n$, så må denne ganges med et primtall $p_2 < \sqrt n$.

Dermed vet vi at hvis vi ikke finner noen primfaktorer $p < \sqrt n$ som deler $n$, så finner vi heller ingen som er større, så vi kan slutte å lete når vi har nådd, og sjekka $\sqrt n$.

Jeg ville vært overraska dersom dette holdt som et bevis, men det var bare en formulering av ideen.

Lagt inn: **09/04-2018 01:03**

Gustav skrev:https://en.wikipedia.org/wiki/AKS_primality_test

Edit: Virker som AKS ikke er en god metode i praksis. En modifisert versjon AKS, av Lenstra og Pomerance, skal visst være rask: https://www.math.dartmouth.edu/~carlp/P ... xity12.pdf . Ellers virker det som probabilistiske tester er raske, som Miller-Rabin og Baillie-PSW https://en.wikipedia.org/wiki/Baillie%E ... ality_test, for å vise at tall er sammensatte.

Jeg dykka litt ned i hullet selv før jeg nå så editen. Det virker som en lett implementerbar metode, men ikke blant de kjappe.

Skal ta en titt på de andre du nevner. Takk!

Lagt inn: **09/04-2018 11:04**

Enkleste og beste opp til relativt store tall er bare å kjøre Miller-Rabbin. Koden under er deterministisk frem til 341550071728321 også er den probabilistisk.

Kode: Velg alt

def _try_composite(a, d, n, s):
    if pow(a, d, n) == 1:
        return False
    for i in range(s):
        if pow(a, 2**i * d, n) == n-1:
            return False
    return True # n  is definitely composite
 
def is_prime(n, _precision_for_huge_n=16):
    if n in _known_primes or n in (0, 1):
        return True
    if any((n % p) == 0 for p in _known_primes):
        return False
    d, s = n - 1, 0
    while not d % 2:
        d, s = d >> 1, s + 1
    # Returns exact according to http://primes.utm.edu/prove/prove2_3.html
    if n < 1373653: 
        return not any(_try_composite(a, d, n, s) for a in (2, 3))
    if n < 25326001: 
        return not any(_try_composite(a, d, n, s) for a in (2, 3, 5))
    if n < 118670087467: 
        if n == 3215031751: 
            return False
        return not any(_try_composite(a, d, n, s) for a in (2, 3, 5, 7))
    if n < 2152302898747: 
        return not any(_try_composite(a, d, n, s) for a in (2, 3, 5, 7, 11))
    if n < 3474749660383: 
        return not any(_try_composite(a, d, n, s) for a in (2, 3, 5, 7, 11, 13))
    if n < 341550071728321: 
        return not any(_try_composite(a, d, n, s) for a in (2, 3, 5, 7, 11, 13, 17))
    # otherwise
    return not any(_try_composite(a, d, n, s) 
                   for a in _known_primes[:_precision_for_huge_n])
 
_known_primes = [2, 3]
_known_primes += [x for x in range(5, 1000, 2) if is_prime(x)]

Lagt inn: **09/04-2018 11:48**

Kode: Velg alt

if n in _known_primes or n in (0, 1):
        return True

Sann for 0 og 1?

Lagt inn: **09/04-2018 13:59**

Tok koden for Rosetta, sjekket ikke så nøye :p

matematikk.net

Raskeste prim-sjekk? (Programmering)

Raskeste prim-sjekk? (Programmering)

Re: Raskeste prim-sjekk? (Programmering)

Re: Raskeste prim-sjekk? (Programmering)

Re: Raskeste prim-sjekk? (Programmering)

Re: Raskeste prim-sjekk? (Programmering)

Re: Raskeste prim-sjekk? (Programmering)

Re: Raskeste prim-sjekk? (Programmering)

Re: Raskeste prim-sjekk? (Programmering)