On Saturday 21 January 2006 12:31, Christian Goetz wrote: > > start with e = 3, a = (), b= () > 1\ decrement all elements of list a by 1 > 2\ test if an element of list a is zero > if no elements are found e is prime > 3\ reset all 0-elements of a to b > 4\ add e to a and b
Where does e get incremented? Otherwise only 3 is being tested ;) Seriously though this just seems to be another formulation of the very well known sieve algorithm for generating lists of primes. > > The advantage of the algorithm is, it uses only trivial operation > (decrement, test if zero, move operations) > The drawback is, it uses a lot of RAM if the numbers to test getting high. Just like the sieve... start with a=(0,2,3,4,5,6,....N), b=() repeat: find x, the first non-zero element in a and append it to b replace the (k.x)th element in a with zero for k=1,2,3,....,floor(N/x) until the first non-zero element in a is greater than sqrt(N) When done b will contain a list of all primes up to N. Note that index jumping by x can be reduced to making a temporary copy of x, then repeating (increment index, decrement x, test if x is zero) until the test is true. Though on current processors integer addition will almost always be faster ;) floor(N/x) never needs to be calculated, just test for the index exceeding N sqrt(N) needs only to be calculated once so the time required can be disregarded provided N is sufficiently large. For listing fairly small primes the sieve algorithm is efficient. Naturally there is a limit imposed by the amount of memory available; we would only be able to sieve up to ~10^80 even if we were able to exploit the whole universe as our memory at a density of one bit per sub-atomic particle. Christian's modified sieve may be slightly more efficient in terms of memory requirements but even having to store only the accumulating list of primes doesn't help a lot, since the Prime Number Theorem states that the number of primes less than N is approximately equal to N/log(N) and log(N) increases vanishingly slowly when N becomes very large. Regards Brian Beesley _______________________________________________ Prime mailing list [email protected] http://hogranch.com/mailman/listinfo/prime
