Abstract |
: |
Three elementary versions of simple prime generating sieves have already been improved by skipping even divisors other than 2. All composite integers are multiples of primes. Taking help of the transitivity property of divisibility allows using the logic that if a prime doesn’t divide a number, then any composite number which is multiple of that prime also cannot divide it. That altogether eliminates the necessity of trying composite numbers for divisibility in primality tests and gives the next generation of prime generating sieves. In fact, the best version of this generation happens to be the celebrated and historic Sieve of Eratosthenes. |