This is where I got the parallel piece from, perhaps I am quoting the wrong person:
"I used 48 parallel sieves, one for each value in the range 0..210 which is not divisible by 2,3,5, or 7" On Tue, Dec 18, 2012 at 10:57 AM, Don <[email protected]> wrote: > No, it does make it faster. > > There are 48 sieves each doing 1/210th of the work which one sieve > would do. Thus it is doing about a quarter as much work. > It means that I don't have to mark values which are multiples of 2,3,5 > or 7. Those values do not appear in the sieve. A simple sieve spends a > large portion of its time on those values because they occur with the > greatest frequency. > I'm not sure what you mean by N workers. I'm not running it in > parallel. It would parallelize very nicely, though. > > Don > > On Dec 18, 10:01 am, Travis Scheponik <[email protected]> wrote: > > That actually doesn't make it "faster" as you claim. You are just > > splitting the work out to N workers, which ignores big O notation > > boundaries. A more appropriate sieve, could be the Euler sieve. > However, > > I am not sure what you mean by create a sieve that ignores the first few > > prime numbers, could you expound on that? > > > > > > > > > > > > > > > > On Tue, Dec 18, 2012 at 9:55 AM, Don <[email protected]> wrote: > > > He is how I did it: > > > > > I used 48 parallel sieves, one for each value in the range 0..210 > > > which is not divisible by 2,3,5, or 7. If those numbers are store in > > > A[48]={1,11,13.17,19,23,...}, then the Nth bit in sieve S represents > > > the value N*210+A[S]. When a new prime P is encountered, you need to > > > find the first place in each of the 48 sieves where it will be > > > encountered. That will be the smallest value V > P^2 where V%210=A[S]. > > > Then to process a sieve you take steps of size 210*P. This is about > > > four times faster than using a single sieve. It could be extended to > > > include multiples of 11, but I didn't do that. > > > > > Don > > > > > On Dec 7, 4:14 pm, Don <[email protected]> wrote: > > > > I know that the Sieve of Eratosthenes is a fast way to find all prime > > > > numbers in a given range. > > > > I noticed that one implementation of a sieve spends a lot of time > > > > marking multiples of small primes as composite. For example, it takes > > > > 1000 times as long to mark off all of the multiples of five as it > > > > takes to mark off the multiples of 5003. In addition, when it is > > > > marking off the multiples of larger primes, most of them are > multiples > > > > of small primes. In fact, if it could skip over multiples of 2,3,5,7, > > > > and 11, the sieve would be about 5 times faster. > > > > > > Can someone describe a way to make a sieve faster by not having to > > > > deal with multiples of the first few prime numbers? > > > > > > Don > > > > > -- > > -- > > > --
