Matematik
Formel til udregning om et tal er et primtal
07. september 2006 af
Scorp-D (Slettet)
Hej
Jeg sidder og er ved at lave et lille program og der mangler jeg en formel som kan tjekke om en variable-værdi er et primtal.
Så jeg ville bare lige spørge om der er nogen som kan give mig et hint til en formel eller ligende som kan udregne dette?
På forhånd tak.
Jeg sidder og er ved at lave et lille program og der mangler jeg en formel som kan tjekke om en variable-værdi er et primtal.
Så jeg ville bare lige spørge om der er nogen som kan give mig et hint til en formel eller ligende som kan udregne dette?
På forhånd tak.
Svar #1
07. september 2006 af fixer (Slettet)
Der er forskellige måder at gøre det på afhængigt af hvor store tal, N, du forventer at skulle teste.
For "meget store" tal N vil jeg anbefale Miller-Rabins test. Den er ikke stensikker, men for de fleste praktiske anvendelser kan der opnåes tilstrækkelig sikkerhed (>99.9999%).
For "mindre tal" N er det tilstrækkeligt checke at sqrt(N) ikke har andre divisorer end 1. Det skyldes, at hvis N har divisoren d > sqrt(N), så vil N/d være mindre end sqrt(N). Derfor kan det ikke betale sig at checke divisorer større end sqrt(N).
For "meget store" tal N vil jeg anbefale Miller-Rabins test. Den er ikke stensikker, men for de fleste praktiske anvendelser kan der opnåes tilstrækkelig sikkerhed (>99.9999%).
For "mindre tal" N er det tilstrækkeligt checke at sqrt(N) ikke har andre divisorer end 1. Det skyldes, at hvis N har divisoren d > sqrt(N), så vil N/d være mindre end sqrt(N). Derfor kan det ikke betale sig at checke divisorer større end sqrt(N).
Skriv et svar til: Formel til udregning om et tal er et primtal
Du skal være logget ind, for at skrive et svar til dette spørgsmål. Klik her for at logge ind.
Har du ikke en bruger på Studieportalen.dk?
Klik her for at oprette en bruger.