Voordeliger qua rekentijd is het wel volgens mij (je hoeft eigenlijk geen enkele deling uit te voeren en alleen maar te schrappen met regelmatige tussenpozen). Memory-consuming is waar, maar echt onmogelijk? Je wil toch ook alle priemgetallen opslaan?
Nee, het is zeker niet voordeliger qua rekentijd. Dat kan ik je vrij eenvoudig uitleggen.
Stel dat we de lijst: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 hebben.
Dan streep je eerst af (2):
2, 4, 6, 8, 10, 12, 14, 16, 18, 20 (hiervoor check je in totaal 18 getallen, je streept er 9 weg, houdt er 11 over).
Daarna streep je af (3):
9 (hiervoor check je in totaal 7 getallen, je streept er 1 weg, je houdt er 10 over).
Daarna streep je af (5):
15 (hiervoor check je in totaal 6 getallen).
Voor de overige getallen moet je nog 10x checken en streep je niets weg.
In totaal check je dan 18 + 7 + 6 + 10 = 41 getallen (met modulo, ofwel delingsrest). En schrap je er in totaal 9 + 1 + 1 = 11 (dat houdt dus ook in dat je 11x een geheugenblok moet gaan verplaatsen, omdat een getal gewist moet worden).
Uiteindelijk houdt je over:
1, 2, 3, 5, 7, 11, 13, 17, 19
In mijn geval, heb je eerst de voorwaarde (nu nog maar één). Ofwel, we beginnen de lijst met de getallen:
1, 2, 3, 5, 7, 11, 13, 17, 19 (sorry, maar per ongeluk allemaal priemgetallen. Maakt in feite niet zo veel uit).
Voor deze lijst worden er per getal twee berekeningen gedaan: 9x2 = 18 berekeningen.
Voor deze lijst worden er: 6 + 5 + 4 + 3 + 2+ 1 = 21 vergelijkingen gedaan.
Voor deze lijst worden er geen memoryblokken gekopiëerd en verplaatst, omdat de getallen pas toegevoegd worden na controle.
Memory-consuming is waar, maar echt onmogelijk? Je wil toch ook alle priemgetallen opslaan?
Niet echt onmogelijk. Maar een beetje irrealistisch om de getallen 1 - 2^31 op te slaan. Dat zou namelijk:
\(2^{31} \cdot 4 bytes = 8.6 \cdot 10^9 bytes = 8GB\)
kosten van het werkgeheugen (een getal kost vier bytes, op 64-bits machines soms 8 bytes). Dat is iets wat jij wss. ook niet in jouw kast hebt zitten en anders zeker niet overhebt voor enkel een afstreeplijst van priemgetallen.
Daarnaast kost een dergelijke lijst opstellen ook eerst heel veel rekentijd. Je moet namelijk eerst van 1 - 2^32-1 tellen. En daarna nog 2^32-1 + 2^32-2 + 2^31 ... om elke keer af te strepen.
Als je overigens ook op Wikipedia kijkt, zie je dat dit vooral een goede methode is voor snel de kleine priemgetallen te berekenen. Dat is dus ook wat ik min of meer denk dat het geval is. Al met al zou ik deze methode niet aanraden.
Maar sowieso bedankt voor het meedenken
.