Hacker News Reader

Comment by burnte | Hacker News Reader

I would doubt it's possible, considering the methods that we use to detect primes come down to brute force. It's hard to build an algorithm when we don't have a formal proof of how primes work/can be detected.

View on HN

Modern prime testing is quite far from brute force. Tests such as AKS[1], ECPP[2], and APR[3] can determine whether a number is prime in polynomial time (in the number of bits/digits), whereas a true brute force search would be exponential.

[1]https://en.wikipedia.org/wiki/AKS_primality_test

[2]https://en.wikipedia.org/wiki/Elliptic_curve_primality_provi...

[3]https://en.wikipedia.org/wiki/Adleman%E2%80%93Pomerance%E2%8...

You're right, I misspoke I should have been more precise and said that out way of finding primes isn't based on a specific theorem or algorithm in that we still have to take a number and demonstrate its primeness.

Well it's definitely possible unless I'm a moron (correct me if I am). If you have the primes up to √n you can find all primes up to n because everything else will be composite of the primes you know already. This is basically what TFA is doing. What I was suggesting is that it would be cool if you could avoid defining rules explicitly for (3n+6), (5n+10), etc and have them appear from some feedback loop where we go from a sequence of primes up to n, to n^2, to n^4...

CSS4, let's do it.

I don't know if CSS is Turing complete already, but I'm pretty sure it would have to be if it allowed you to implement something like that...

No, it would only need to be primitive recursive [0] because you can bound its runtime. There's actually a lot you can do without Turing completeness.

[0]: https://en.wikipedia.org/wiki/Primitive_recursive_function#C...

Pure CSS game: https://codepen.io/elad2412/pen/hBaqo

Rule110 (After setting first row requires alternation of tab/space to run): https://codepen.io/elrumordelaluz/pen/wqLyH?editors=010

stackoverflow discussion: https://stackoverflow.com/questions/2497146/is-css-turing-co...

Reply on news.ycombinator.com