Primtal - Erastothenes' si

Hvad mener du med "nemmeste".

Lad os sige, at du vil finde alle primtal < 1000, så er E's si hurtig for en computer, fordi tallene er repræsenteret ved 1000 bit. Hvis nu computeren, som vi kan sige er en 32-bit computer, starter med at fjerne alle de tal, som 2 går op i, så danner computeren et register med indholdet i bits: 01010101010101010101010101010101. Dette indhold and'er den med et 1000 bit array i memory, altså behandler den 32 bit / pr instruktion alias 32 primtalskandidater.

På samme måde danner den et bit-mønster for at fjerne de tal, som 3 går op i:  . . . 110110110 . . . , som den så "stempler" ned i memory, 32-bit ( primtals-kandidater ) ad gangen.

Denne metode er altså hurtig, når der skal findes få primtal.

Når antallet af primtal, der skal findes forøges, vil E's si medføre, at afstanden mellem resterende primtalskandidater forøges, og computeren vil bruge næsten al sin tid på at fjerne kandidater, der allerede er fjernet. Derfor er jeg sikker på, at andre, forfinede metoder vil "overhale" E's si her.

det jeg mente med nemmeste var, den mest basale måde eller den mest simple måde at finde primtal på. Du må meget gerne stadig svare på dette, men udover det tak for svaret. :)

Du kan også simpelthen gå tallene igennem og teste om de er primtal. Det eneste lige tal, der er et primtal er 2, så du kan halvere arbejdet ved kun at teste uligetal.

Hvis du gemmer primtallene kan du simpelthen se om disse går op i tallene. Den egentlige lettelse er at du kun behæver at teste med tal, der er mindre end kvadratroden af det tal du tester.. Hvis tallet du tester er t og p1 og p2 er primta derer større end kvadratroden af t vil p₁*p₂ > t i modstrid med at de begge skulle gå op