[mikejb]

I don't feel really negatively towards this project, but after reading the title and looking at the code it felt a bit disappointing. When I read "computing primes" I didn't expect so much pre-computation cooked into the code.

[kafkaesq]

It's what you might call a "halfway algorithm" -- yes it needs some major fudging baked in (because from what I understand you can't do things iteratively in CSS). But it does, intrinsically, compute the primes. And the point is it demonstrates a kind of computation one normally wouldn't think was even possible with CSS (that is: not that you'd rule it out as beyond the computational reach of CSS; but it's definitely the sort of computation you normally wouldn't think to do with CSS).

So I'd say it's definitely a valid hack.

[brudgers]

I don't disagree, because I have a similar feeling. But I recognize that it comes from a bit of a 'No True Scotsman' in regard to computation.

By which I mean that looking up values in a table is actually a part of computation. That's pretty much how anything with a trigonometric function works [we've just replaced books with integrated circuits]. Back in the days of using a slide rule, there was a looking it up in a table element as well, it's just that the table was in a flexible form.

Practically, speaking if the easiest way to calculate the first fifty million primes might be: https://primes.utm.edu/lists/small/millions/

Philosophically, I don't have the same feeling querying for some nth prime at https://primes.utm.edu/nthprime/index.php but it's probably doing all its calculations for mundane things like network packets and none of it sieving natural numbers.

[mikejb]

I see your point, and I think we share a point of view.

But when using lookup tables, I consider the computation of the lookup table a part of the algorithm - after all, a lookup table is essentially an optimization: You extract a sub-computation and store it, paying with space for better time complexity.

[brudgers]

Philosophically, I don't think that feeling intellectually satisfying is a marker of correct understanding. I mean I don't think there's anything out in independent reality that makes an procedure that implements the sieve of Eratosthenes better than a procedure that uses lookup tables.

1. The only thing that matters about a function 'nth-prime' is that it maps 1->2, 2->3, 3->5 etc.

2. To be useful in practical applications, a function `is-prime` is unlikely to use the sieve of Eratosthenes and more likely to use something like Fermat's Primality Test [1] and hence will be mistaken over Carmichael Numbers and so hard coding the first few into the function via looking might be a good way to do what people expect...though at some point:

Numbers that fool the Fermat test are called Carmichael numbers, and little is known about them other than that they are extremely rare. There are 255 Carmichael numbers below 100,000,000. The smallest few are 561, 1105, 1729, 2465, 2821, and 6601. In testing primality of very large numbers chosen at random, the chance of stumbling upon a value that fools the Fermat test is less than the chance that cosmic radiation will cause the computer to make an error in carrying out a “correct” algorithm. Considering an algorithm to be inadequate for the first reason but not for the second illustrates the difference between mathematics and engineering. Abelson, Sussman, Sussman https://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.htm...

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

[nedbat]

What pre-computation do you see there? There are the numbers 1-999, and the numbers 2-32.

[mikejb]

I see an iteration of every possible factor for the numbers given. Continuing from 999 further on to 1400, the code doesn't work anymore (It claims 1369 to be prime).

So, to be precise, the code does not compute 'primes', the code lists every number that is not devisable by any number from 2 to 32.

[nedbat]

There is a precomputation that 32 is the (rough) square root of 1000. There is no precomputation of primes. It is true that the code will not work beyond 1000, unless you also add more selectors.