The usual method of generating the primes below N is to use a prime number sieve, such as the Sieve of Eratosthenes. This requires O(N log log N) operations for a random access machine, but can be reduced to O(N) by refining the algorithm. There is an implementation in Conway’s Game of Life that generates the primes in linear time, O(N), utilising the potential for parallel processing:
A more efficient prime number sieve is the Sieve of Atkin. This involves counting the number of solutions to certain quadratic Diophantine equations, and (when optimised) has an asymptotic time complexity of O(N/log log N). An efficient implementation generates all primes below 10^9 in just eight seconds.
Nevertheless, a new prime-generating machine has since been discovered. Bizarrely, it was expected to output natural logs, but instead produces the primes in succession. An online demonstration of the machine is included here. It is estimated that it would claim the EFF prize of 150000 USD for a 100-million-digit prime long before the year 10^10^8.