New prime-generating algorithm

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.

Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.

4 Responses to New prime-generating algorithm

  1. Pingback: Project Euler Problem#10 solution in C++ | Khuram Ali

  2. Thomas says:

    So, exactly what is the asymptotic time complexity of the improved algorithm?

    • apgoucher says:

      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).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s