WANTED:Program for primenumbers

[Robert Cousins]

In article <1659 at eds.ericsson.se> rif_xu at eds.ericsson.se writes:
>
>	Hi,
>	does anybody out there in Netland have a program 
>	(preferably written i C or Pascal) which finds 
>	primenumbers from 1 to a-very-big-number (I have the
>	Sieve of E. but I can't generate those big primes I
>	want on a MacII-maximum up to 50000).
>	
>
>	Thanks Sigge

I published an algorithm derived from the Erotosthenes Sieve in the
Sept (oct?) '87 COMPUTER.  The major difference is that it worked for
VERY large ranges and was suitable for parallel or serial execution.
The actual program is only about 30-40 lines long (and I don't haveit
on line right now), so it shouldn't take but an hour or so to write it.
The idea is simple:

	You know that a number is prime if it has no factors which are
	greater than 1 and less than or equal to the square root of the 
	number.  Therefore, to sieve numbers from 1 to a million, you need
	only to create a list of prime factors from 1 to 1000.  This
	list of primes can then be used in a second sieve.  

The beauty of this approach is that once the primes from 1 to 1000 are 
known, you can pick any region in the range 1000 to 1000000 and sieve
it using ONLY THESE PRIMES.  (In fact, you can trim the list so that
you only use values <= the square root of the upper bound of the region.)

This is very suitable for parallel computation.  Imagine a twenty CPU 
machine (that is what I debugged it on) with 20 copies of the program.
Each program simultaneously sieves from 1 to 1000 building up a table.
Then, each program decides which one of the CPUs it is (0-19) and then
chooses a region in the remaining space from 1000 to 1000000 to sieve.
This second sieve pass is slower by about 50x.  Alternately, 20 passes
could have been run on a single CPU since no state info is required
to be saved between passes.

If your MAC can sieve up to 50K numbers the old fashioned way, then you
can now sieve numbers up to 2.5e9 with one pass and using a second pass
you can do 1.25e14.  Probably large enough for you.  My experience was
that these runtimes could be measured in a few minutes.  

If you need more help than this, email me and I'll try to find the code.
(Or I'll just whip it up again. :-)

Robert Cousins
Dept. Mgr, Workstation Dev't.
Data General Corp.

Speaking for myself alone.