9 ms·
Code size increases in Θ(n^(0.5)) I agree that the title is somewhat misleading - it is (to me) as much a 'computation of prime numbers' as a lookup table woul
by mikejb 10y ago
Code size increases in Θ(n^(0.5))
I agree that the title is somewhat misleading - it is (to me) as much a 'computation of prime numbers' as a lookup table would be.
- orf 10y agoWouldn't a bit of js to create them on the fly stop that? It would still be a kind of lookup table though.
- mikejb 10y agoI think using JavaScript would move the concept even further away from "computing primes with CSS". It would just do some things on the fly that the author did with python.
- bonzini 10y agoFWIW, this[1] is closer to how a "real" sieve of Eratosthenes program might look like, with three optimizations: 1) omitting even numbers from the sieve, 2) sieving starting at n^2, 3) precomputing primes up to sqrt(n) if you want to sieve up to n. The code size then is Θ(sqrt(pi(n)). [1] https://jsfiddle.net/L8mxuag5/1/ https://jsfiddle.net/L8mxuag5/1/
- contravariant 10y agoWell it's closer to O((n/log(n))^0.5), although that doesn't make much of a difference until n becomes rather large.
- mikejb 10y agoGood catch - I didn't differentiation between n as 'upper limit for primes' and n as 'input length'. The former is more intuitive, which makes your solution more accurate. (Also, I should have played it safe and use O instead of Θ...)