Sieving är ett sätt att generera primtalen: man börjar med 2 och stryker alla multiplar av 2 tills man passerat ett tal som inte stryks. Detta tal blir nästa primtal. Sedan stryker man alla multiplar av 2 och 3 tills man passerat ett nytt tal som inte stryks. Detta tal (5) blir vårt nästa primtal, och så vidare.
Hur många operationer krävs för att beräkna de n första primtalen? Är det logaritmiskt ökande på n? Är det exponentiellt ökande? Ger primtalssatsen någon fingervisning?
Det finns fler än en algoritm för det där. Antal operationer blir nog en fråga om definitioner för dels så är det en balans mellan rum och tid, så ju mer minne man har att utnyttja desto kortare tid tar det men även om man vill bryta ner de matematiska operationerna i sina minsta delar så är det inte helt uppenbart hur det appliceras på en dator vars logiska kretsar kanske kräver olika många steg för olika matematiska operationer, där man därutöver behöver någon mjukvarustruktur som kontrollerar och ordnar resultaten.
Det finns både logaritmiskt ökande och linjärt ökande, men eftersom det också beror på komplexiteten i algoritmen och förhållandet mellan antal platser samt tid så säger inte det någonting om hur lång tid en algoritm behöver för något antal operationer, utan en algoritm med mindre komplexitet kan vara snabbare för mindre primtal medans en algoritm med större komplexitet kan vara snabbare för större primtal. Så oavsett om man vill prata om en operation som en logisk krets utför eller en matematisk operation som krävt en serie logiska steg så är det balans mellan flera saker.
Sieving är ett sätt att generera primtalen: man börjar med 2 och stryker alla multiplar av 2 tills man passerat ett tal som inte stryks. Detta tal blir nästa primtal. Sedan stryker man alla multiplar av 2 och 3 tills man passerat ett nytt tal som inte stryks. Detta tal (5) blir vårt nästa primtal, och så vidare.
Hur många operationer krävs för att beräkna de n första primtalen? Är det logaritmiskt ökande på n? Är det exponentiellt ökande? Ger primtalssatsen någon fingervisning?
Jag gissar att primtalssatsen ger iaf en antydan till svar. https://sv.wikipedia.org/wiki/Primtalssatsen
Om π(x) definieras som antalet primtal som är mindre än eller lika med x, så säger satsen att
π(x) ≈ x/ln(x)
med allt större överensstämmelse ju större x är.
För att vara exakt säger satsen att
lim_{x→∞}π(x)/(x/ln(x)) = 1.
Med den metod du beskriver krävs iaf i runda slängar x operationer för att undersöka alla tal upp t o m x, vilket då ger alla n=π(x) primtal upp t o m x. Svaret på frågan ges i så fall av lösningen x på ekvationen
π(x) = n
eller approximativt av lösningen x till
x/ln(x) = n
som dock måste lösas numeriskt.
---
Enkel och ganska snabb numerisk lösning till ekvationen ovan.
x₀ = n
x₁ = n ln x₀
x₂ = n ln x₁
...
__________________
Senast redigerad av nerdnerd 2021-04-17 kl. 16:32.
Jag letade lite snabbt upp en artikel vid namn Trading Time for Space in Prime Number Sieves i tidsskriften Algorithmic Number Theory. Den är förmodligen inaktuell, eftersom den skrevs för över 20 år sedan, men där kan man i alla fall få en fingervisning av tids- och minneskomplexiteten för olika såll.
Citat:
The fastest known prime number sieve is the dynamic wheel sieve of Pritchard [11], which uses O(n/log log n) arithmetic operations and O(n/log log n) bits of space. Dunten, Jones, and Sorenson [6] gave an algorithm with the same asymptotic running time, while using only O(n/(log n log log n)) bits of space. Pritchard also invented a segmented wheel-based sieve that requires O(n) operations and only O(sqrt(n)/log log n) bits of space [12]. This last sieve is more practical for larger values of n, because space becomes a serious concern when n exceeds, say, 10^7.
