Primtal

Hej!

Om du har ett udda heltal ($N$) som vill testa är primtal så behöver du undersöka om primtalen 3, 5, 7, 11, 13, ..., $\sqrt{N}$ delar talet $N.$ Om inget av dem gör det så är $N$ ett primtal.

För att undersöka om 107 är ett primtal ska du alltså beräkna kvadratroten $\sqrt{107} \approx 10.34.$ Du ska alltså undersöka om primtalen 3, 5, 7 delar talet 107; primtalet 11 är större än $\sqrt{107}$ 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!