Primtal
Hej!
Jag undrar hur man vet om ett tal är ett primtal eller inte, jag läste lite på matteboken.se och där det står att man kan använda sig av Eratosthens såll. Men om det gäller ett större tal, säg 107. Finns det något smidigt sätt att ta reda på om stora tal är primtal eller inte?
Hej!
Om du har ett udda heltal () som vill testa är primtal så behöver du undersöka om primtalen 3, 5, 7, 11, 13, ..., delar talet Om inget av dem gör det så är ett primtal.
För att undersöka om 107 är ett primtal ska du alltså beräkna kvadratroten Du ska alltså undersöka om primtalen 3, 5, 7 delar talet 107; primtalet 11 är större än och behöver därför inte undersökas. Om inget av dem gör det så är 107 ett primtal.
Albiki
Att avgöra om stora tal är primtal eller inte (eg: att faktorisera ett stort tal), är ett kvalificerat svårt problem.
Det finns alltså verkligen inget smidigt sätt. Tal med upp till 16-18 (jag gissar lite) siffror kan en vanlig dator enkelt avgöra om det är ett primtal. Sedan blir det snabbt mycket svårare.
Mycket IT-säkerhet och kryptering i världen bygger på just detta. Om du vill kan du läsa om RSA.
Tack för er hjälp!
