rif_xu@eds.ericsson.se (07/19/89)
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
rec@dg.dg.com (Robert Cousins) (07/21/89)
In article <1659@eds.ericsson.se> rif_xu@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.