Prime number generation is vital to prime factorization and primality testing, and is also used for generating random numbers. Prime number generation gives a better understanding of the fascinating nature of prime numbers which helps to generate large primes which are used in public key cryptosystems for e-security. Further, prime number generation involves heavy number crunching, thus it is also used as a benchmark for comparing the hardware performance and the capabilities of compilers. Prime number generation programs are among the choicest programs for demonstrating programming basics to beginners. The present paper thus discusses some commonly used techniques of generating prime numbers employing the sieve theory. It begins with the famous Sieve of Eratosthenes (SoE) and discusses some of its efficient extensions. The paper also provides an overview of the Pritchard's wheel sieve technique. Finally we provide a comparative complexity analysis of the SoE and its quoted extensions.

Historically the problem of prime number generation (prime generation) from two to a desired limit N had little practical value and was a highly hyped and important problem of the number theory only. However, the advent of public key cryptosystems like the Rivest, Shamir and Adleman (RSA) algorithm led to an awakening of more general interest in prime generation. Large prime numbers formed the basis of these public key data security systems. Also with advances in computer hardware, the interest in prime generation grew further among computer scientists and engineers because they realized prime generation as a convenient benchmark against which several aspects of a computer’s performance, such as, memory access time, the speed at which indexing is done, and the overhead of looping can be measured. Specifically, the prime generating sieves test the power of a machine or a compiler to access a very large array in memory rapidly and repeatedly. By implementing the prime generation in parallel, the parallel execution capabilities of modern computers and compilers (Sun Studio Express, 2007) can also be accessed and evaluated. It has been seen over the years in many professional journals and popular computer magazines that numerous prime generating sieves have been used as benchmarks (Bokhari, 1987; and Crandall and Pomerance, 2001). Interest in primes increased further by the recent proof that primality testing is in P (Agrawal et al., 2004).

Also it is known that prime generation is vital to prime factorization of numbers, hashing of keys and primality testing. Prime generation however still remains computationally expensive. For cryptographic algorithms, like the RSA algorithm, which depend on large prime numbers, the computation cost of generating large prime numbers is huge even with today’s high performance computers. So in order to fully appreciate the beauty of prime numbers and their importance one must first appreciate the complexity of both producing and identifying the prime numbers.

Prime generation can be done by various approaches: randomly generating a number and checking for primality using probabilistic methods as in Rabin-Miller test, or using deterministic tests like Agrawal-Kayal-Saxena (AKS) primality test, the generating primes having special properties like the set of Mersenne primes or generating all primes in particular intervals using known or proven conjectures. However, for generating all primes deterministically, in the interval [2, N], no known series, formula or conjecture has been devised till date to find them all. Till date the sieve approach is prominently in use to solve this problem. Thus it makes it even more important to study the sieve approach of prime generation.

Computer Sciences Journal, Prime Generating Sieves, Prime Number Generation, Public Key Data Security Systems, Cryptographic Algorithms, Conventional Strategies, Software Optimization Tools, Psyco Optimization, Trial Division Techniques, Prime Number Sieves, Wheel Factorization.