News for hackers. Stuff that matters.
Re:Computing primes with CSS by amelius on Friday September 30, 2016 @05:18AM (#12611365)
How does the size of the code increase with the number of primes shown?

Imho, the code should not grow. So in my view, the article is cheating.

Re:Computing primes with CSS by mikejb on Friday September 30, 2016 @05:34AM (#12611405)
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.

Re:Computing primes with CSS by bonzini on Friday September 30, 2016 @06:45AM (#12611650)
FWIW, 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/

Re:Computing primes with CSS by contravariant on Friday September 30, 2016 @07:50AM (#12611889)
Well it's closer to O((n/log(n))^0.5), although that doesn't make much of a difference until n becomes rather large.
Re:Computing primes with CSS by mikejb on Friday September 30, 2016 @08:58AM (#12612160)
Good 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 Θ...)
Re:Computing primes with CSS by orf on Friday September 30, 2016 @05:41AM (#12611423)
Wouldn't a bit of js to create them on the fly stop that? It would still be a kind of lookup table though.
Re:Computing primes with CSS by mikejb on Friday September 30, 2016 @05:54AM (#12611467)
I 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.