[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