NewPGen is a program used by researchers looking for large prime numbers. It is a program that is used to rapidly presieve a set of candidate numbers, removing those that are definitely composite numbers. It does this by removing those numbers divisible by 3, 5, etc, but since it works with a large set of numbers (and uses some clever algorithms and fast implementations), it is a lot better than performing trial division on each number in the set. Those numbers which get through this sieve are then be tested with a primality proving program to find the primes.

NewPGen has been used to make many discoveries in the realm of prime numbers, for example the largest known twin primes, and nearly all of the known cunningham chains. It is written and maintained by Paul Jobling.

External links:

• The Prime Pages: NewPGen, http://primes.utm.edu/programs/NewPGen/

See also

• Sieve of Eratosthenes