The Prime Number Theorem was conjectured by Gauss from looking (*very hard*, one can presume...) at a table of the primes $\leq10^6$. It is not with too much effort that one can read his *Disquisitiones* as a set of tricks to determine primality with as little work as possible, and one can understand the motivation: he was his own computer, in a way :P

(I don't know where Legendre got the statement from, but he must surely have had tables of primes too!)