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:
[youtube=http://www.youtube.com/watch?v=68nEX5CEmZE]
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.
Pingback: Project Euler Problem#10 solution in C++ | Khuram Ali
So, exactly what is the asymptotic time complexity of the improved algorithm?
Hmm… April Fool jokes are less relevant when one sees them several months later.
I think that I was arguing that the bear produced primes in linear time (which is of course impossible, given that the length of the output is superlinear).
woops, forgot to check the date this was posted