## fast java prime number generation

So I found some old prime number generation code and decided to spruce it up. I also wanted to benchmark the **BitSet vs a boolean array** as I had previously had issues with a boolean array. Six methods tried:

### Prime Generators - Source Download

**Simp**- Simply check for all x’s 0 to maxPrime if x is prime. ie check x isn’t divisible by any number between 2 to x-1.**SimpOdd**- same as above, but add 2 to list of known primes, then check all x’s between 0 and maxPrime but stepping in 2’s. And only check for divisibles between 2 to x/2.**S - Sieve**- Sieve of Eratosthenes**SS - SkippingSievePG**- improve speed by taking advantage that even numbers are never prime except 2. Therefore when sieving using the prime 3, instead of sieving 6,9,12,15,18,21 we can actually sieve 9,15,21 ie jump double our prime each time.**OSS - OddSkippingSievePG**- Same as above BUT improve speed/memory making the boolean array represent odd numbers instead of all numbers.**BSOSS - BitSetOddSkippingSievePG**- Same as above but use BitSet instead of boolean array

## Seconds taken to generate primes between 0 to 10,000,000

Speed of simp’s were so slow as to be unusable for finding large numbers of primes, ie 1000’s of times slower than sieves.

## Memory required to generate primes between 0 to 10,000,000

Notice 1,120,000 Bytes needed to store arraylist of integers.

### Size of boolean arrays / BitSets in Java

boolean arrays in java use 1 byte per true/false value. BitSets use 1 bit per true/false value (may depend on OS/VM). However BitSets are slower to access. This explains why BitSetOddSkippingSievePG was slower than OddSkippingSievePG but required less memory.

### Use a sieve - to generate primes fast

## Further Improvements

The idea of reducing the array size by letting the array represent odd numbers could be generalized. Further speed increases are also possible. If you want to know more see wheel factorization or segmented sieves. If you code a quicker prime generator please let me know.