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?
Raskeste prim-sjekk? (Programmering)
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
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.
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.
-
- Noether
- Innlegg: 24
- Registrert: 26/03-2018 18:50
Jeg har ikke et svar, men jeg lurte på hvorfor man ikke trenger å sjekke lengre enn til [tex]\sqrt{n}[/tex] ?
[tex]\ln(-1)=i\pi[/tex]
Kort sagt:Leonhard_Euler skrev:Jeg har ikke et svar, men jeg lurte på hvorfor man ikke trenger å sjekke lengre enn til [tex]\sqrt{n}[/tex] ?
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.
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.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.
Skal ta en titt på de andre du nevner. Takk!
-
- Fibonacci
- Innlegg: 5648
- Registrert: 24/05-2009 14:16
- Sted: NTNU
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)]
"Å vite hva man ikke vet er og en slags allvitenhet" - Piet Hein
https://s.ntnu.no/Integralkokeboken
Lektor - Matematikk, Fysikk og Informatikk
https://s.ntnu.no/Integralkokeboken
Lektor - Matematikk, Fysikk og Informatikk
Kode: Velg alt
if n in _known_primes or n in (0, 1):
return True
-
- Fibonacci
- Innlegg: 5648
- Registrert: 24/05-2009 14:16
- Sted: NTNU
Tok koden for Rosetta, sjekket ikke så nøye :p
"Å vite hva man ikke vet er og en slags allvitenhet" - Piet Hein
https://s.ntnu.no/Integralkokeboken
Lektor - Matematikk, Fysikk og Informatikk
https://s.ntnu.no/Integralkokeboken
Lektor - Matematikk, Fysikk og Informatikk