To speed things up I moved to c++ and implemented the same algorithm, and played around with using vectors to store the list of primes. That sped it up some, but it would still eventually get bogged down by the algorithm.

So finally I decided to implement the Sieve of Eratosthenes using a bit array. Now that got things going quickly. It is a fast algorithm that is pretty much bound by the amount of memory you have. On my home system it did the following for an upper bound of 1 billion:

```
snits@perelman:~/proj/cpp=>time ./se 1000000000
50847534 primes between 2 and 1000000000. Greatest prime is 999999937
real 1m58.563s
user 1m58.352s
sys 0m0.101s
```

I bumped the upper bound up to 40 billion, which would take a fair chunk of my RAM for the bit array, and it had the following results:

```
snits@perelman:~/proj/cpp=>time ./se 40000000000
1711955433 primes between 2 and 40000000000. Greatest prime is 39999999979
real 90m48.631s
user 90m40.850s
sys 0m3.589s
```

## No comments:

## Post a Comment