By the prime counting function, there are about (2^4096)/ln(2^4096), or close enough to 2^4085 prime numbers under 2^4096, which is close enough to 10^1360 to not sweat the piddly factors that may be off by.
I'd tell you to "go ahead and start computing that and tell me when you're done", however, I like the universe I live in, and the entire information content of the boundary of the observable universe is something like 4*10^122 bits [1]. So you're talking about creating a black hole vastly, vastly, vastly, 10-to-the-power-of-thousand+ times larger than the observable universe, which some of your fellow universe residents may find to be a hostile act and we probably aren't going to let you finish.
While you can define such a table as having "O(1)" lookup properties in the sense that on average the vast, vast, vast, vast, vast, dwarfing-the-observable-universe-by-hundreds-of-orders-of-magnitude light years you'd have to travel for the answer to a given query can be considered "O(1)" since it's on average pretty much the same for all lookups, it's constant in a rather useless sense.
The idea is to do it once. A lot can likely be compressed, while keeping access time log-linear. Store it passively, so that it won't need power except for reading, like mask ROM or CD-ROM do not.
No cryptographer cares about time-complexity on its own. Even the naive asymptotic cost-model is `t * (P + M)`, where P is the number of processors and M the amount of memory (including ROM/code-size). And a more serious cost-model is `t * A` where A is the chip area (~transistor count). This considers less obvious costs, like the size of the memory access circuitry, which can be substantial when you have a large number of parallel processors.
In any of these models the time would be multiplied with the size of the lookup table, resulting in a cost much higher that number-field-sieve.
Plus you need to consider the (amortized) cost of populating the lookup table.
