Matematik

Prime

29. august 2007 af math-freak++ (Slettet)

er 1357 et primtal? Skal jeg teste det via Fermats sætning? Det tager nemlig langt tid..

Brugbart svar (0)

Svar #1
29. august 2007 af Peden (Slettet)

Google er din ven...
http://www.prime-numbers.org/

Svar #2
29. august 2007 af math-freak++ (Slettet)

#1 Det link giver mig intet..

Brugbart svar (0)

Svar #3
29. august 2007 af Hindsborg (Slettet)

Det er ikke et primtal. Pedens (#1) link virker som ganske fint.

Brugbart svar (0)

Svar #4
29. august 2007 af Peden (Slettet)

Intet? Kan du ikke se siden?
I følge den side er tallet ikke et primtal ;)

Brugbart svar (0)

Svar #5
29. august 2007 af Peden (Slettet)

Men det var i virkeligheden ikke det du ville vide var det? Ville du gerne vide HVORDAN man i hånden finder ud af om det er et primtal?

Svar #6
29. august 2007 af math-freak++ (Slettet)

#5 Ja, netop. Jeg kan godt se siden men jeg vil gerne vide hvordan det gøres. Jeg kan godt ved Fermats lille sætning, men den tager bare langt tid ved store tal!

Brugbart svar (0)

Svar #7
29. august 2007 af Peden (Slettet)

http://www.lessonplanspage.com/MathPrimeVsCompositeNumbers7HS.htm

Svar #8
29. august 2007 af math-freak++ (Slettet)

#7 Okay, men det link er ikke spor matematisk. Det er mere avanceret end man regner med.

Brugbart svar (0)

Svar #9
29. august 2007 af peter lind

Fermats lille sætning kan ikke bruges, da man godt kan komme ud for at den er opfyldt selv om p ikke er et primtal. Så vidt jeg husker er 2^340 mod 341 = 1 selvom 341= 11*31.
For store tal bruger man et resultat af en udvidelse af Fermats sætning.
Man beregner a^( (p-1)/2) mod p, a^( (p-1)/4) mod p, a^( (p-1)/8) mod p o.s.v for alle der giver a opløftet i en heltalspotens. Hvis p er et primtal, skal enten alle give resultatet 1 eller også skal en af dem give resultatet p-1 eller -1 om man vil. Dette giver heller ikke helt sikkert en garanti for at p er et primtal, så man tester for forskellige værdier af a. Man kan vise at hvis man tester med tilstrækkelig mange a'er er sandsynligheden for at man fejlagtig accepterer et tal som primtal, så lille at man ser bort fra det.
Der er altså ikke nogen nemme løsninger til det. Skal man test store tal er det helt nødvendigt at bruge et program.
Med et så lille tal som 1357 kan det nu ret nemt gøres i hånden. Du behøver kun teste om primtal mindre end kvrod(1357) går op i 1357.
Det er overkommelig med en lommeregner.

Svar #10
29. august 2007 af math-freak++ (Slettet)

Det giver vel ca. 35?

Svar #11
29. august 2007 af math-freak++ (Slettet)

Men hvordan kender jeg primtal mindre end 1357^0,5 ? Hvilke tal skal vælges?

Brugbart svar (0)

Svar #12
29. august 2007 af peter lind

Du skal teste tal mindre end 37. Med hensyn til hvilken tal du skal teste med, kan du udelade alle andre lige tal end 2, alle tal der ender på 5 bortset fra 5 selv. Det er faktisk let at udelade de fleste. Hvis der findes ulige tal, som du ikke ved er primtal så test med det. Det koster kun lidt ekstra tid. Tallene du skal teste med er 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 og 31.

Svar #13
29. august 2007 af math-freak++ (Slettet)

#12 Det er jo smart! Hvordan nåede du frem til den metode?

Svar #14
29. august 2007 af math-freak++ (Slettet)

Okay, 23 går op i det. Jeg kan se , at man kan bruge din metode til at afgrænse tallets (mulige eksisterende) primfaktoropløsning. Opløsningen kan så åbenbart ikke overskrive tallets (1357) kvadratrod.

Brugbart svar (0)

Svar #15
30. august 2007 af Mandelbrot (Slettet)

#14 Prøv at læse linket i #7 igen. Der står det du spørger om.

Brugbart svar (0)

Svar #16
30. august 2007 af peter lind

#14
Lad p1 og p2 være faktorer i et tal T. Hvis p1 > kvrod(T) og
p2 > kvrod(T) så vil p1*p2 > kvrod(T)*kvrod(T) = T. Mindst en af faktorerne må altså være mindre end kvrod(T)

Skriv et svar til: Prime

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.