Euler's Sieve

[storm5510]

A) Start with all the natural numbers except '1' which is not a prime.
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35...
^
B) The leftmost number is prime. Multiply each number in the list by this prime and discard the products.
2 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35...
^
C) The number after the previous prime is also a prime. Multiply each number in the list starting from
the latest prime by the latest prime and discard the products.
2 3 5 7 11 13 17 19 23 25 29 31 35...
^
Repeat C) indefinitely. On each repetition a new prime is identified (marked ^) until all the primes in
the starting list have been found.

I can't follow this. Perhaps someone could elaborate?

[Mini-Geek]

Should retain the original spaces to be clearer:

A) Start with all the natural numbers except '1' which is not a prime.
  2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35...
  ^
B) The leftmost number is prime. Multiply each number in the list by this prime and discard the products.
  2 3   5   7   9    11    13    15    17    19    21    23    25    27    29    31    33    35...
    ^
C) The number after the previous prime is also a prime. Multiply each number in the list starting from
   the latest prime by the latest prime and discard the products.
  2 3   5   7        11    13          17    19          23    25          29    31          35...
        ^
Repeat C) indefinitely. On each repetition a new prime is identified (marked ^) until all the primes in
the starting list have been found.

Let's look at step B:
First, copy the line of numbers at B to C. We'll be reading off of the B line, and eliminating them from the C line. The prime we're working on is 3, so first we eliminate 3*3=9. The next number on the list is 3*5=15, eliminate that too, next is 3*7=21, then 3*9=27 (even though 9 is eliminated for next time, it's still in line B, so it needs to be eliminated too), and so on.
Once we reach the end of the list, restart it with copying C to D, reading from C (starting at 5*5=25), and crossing off from D.
Repeat until either:
1. you reach the final number/prime on the list, or
2. (will save some work) until the first number you try to eliminate in that sequence is higher than the largest prime. (i.e. [prime you're eliminating] > sqrt([max number on list]), in this case 7, so stop when you find 7*7>35)
(same result either way)

[storm5510]

In order to create a computer algorithm, one must be able to maintain the list indefinitely. After a while, the list would grow so large that the advantages of using the list would become nil.

[Primeinator]

Originally Posted by storm5510

In order to create a computer algorithm, one must be able to maintain the list indefinitely. After a while, the list would grow so large that the advantages of using the list would become nil.

Which is precisely why we can't just automatically find the "next" Mersenne Prime.

[storm5510]

As computer technology continues to evolve, perhaps some of this limitation can be overcome. Take the hardware advances and add new ways to to write applications. Who is to say what will be available in the years to come.

[cheesehead]

Originally Posted by storm5510

As computer technology continues to evolve, perhaps some of this limitation can be overcome. Take the hardware advances and add new ways to to write applications. Who is to say what will be available in the years to come.

There are some fundamental limitations to technology.

For instance (as explained here: http://mersennewiki.org/index.php/Lu...le_Explanation)

The number of particles (electrons, protons, neutrons, muons, etc.) in the known universe is less than 10¹⁰⁰, according to recent estimates. 10¹⁰⁰ is less than 2⁴⁰⁰. So if we could use every particle in the known universe to store one binary bit of information, the largest number whose binary (or decimal) expansion we could store would be less than 2^2[sup]400[/sup]

... but we'll probably not approach that limitation for a while.

[CRGreathouse]

Of course with quantum methods the limit becomes a number with that many bits (adding another level to the power tower).

[xilman]

Originally Posted by CRGreathouse

Of course with quantum methods the limit becomes a number with that many bits (adding another level to the power tower).

Of course, with quantum methods the limit becomes a number with a countably infinite number of bits. Further, a single hydrogen atom may store that number of bits.

Paul

[storm5510]

It may be that, some day, CPU's will be able to do "BigNum" math without any special software considerations. The ALU in the CPU will be able to handle it all. That may be in the future a ways though; probably not high on Intel's and AMD's to-do list.

[CRGreathouse]

Originally Posted by xilman

Of course, with quantum methods the limit becomes a number with a countably infinite number of bits. Further, a single hydrogen atom may store that number of bits.

So much for upper bounds?

[Orgasmic Troll]

Originally Posted by xilman

Of course, with quantum methods the limit becomes a number with a countably infinite number of bits. Further, a single hydrogen atom may store that number of bits.

Paul

how?