Sieve of Erastothenes
Sieve of Erastothenes@Oregonstate
Prime numbers are found by Sieve of Erastosthenes as follows:
- A bit map is an array of bits.
- A bit map is implemented as a BitSet in Java.
- Each number smaller than or equal to N is represented by one bit in the Bitsetp of size N + 1. The bit for a number is 0 if the number is a prime.
- Otherwise, it is 1.
- 0 and 1 are non-prime numbers, and 2 is a prime number.
- Multiples of each prime number is marked nond-prime numbers.
- All the prime numbers between 2 and N / 2 are considered.
(Courtesy of http://web.engr.oregonstate.edu/~minoura/cs261/)
|