[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