This page is sponsored by
http://www.A-Wee-Bit-of-Ireland.com/.^{™}
Your source in the USA for the finest
http://site.aweebitofireland.com/
Irish caps and hats.
All
products made in Ireland.

**
If you want many primes or larger primes, my
JAVA prime number program might be better than this program
because it will run on your computer instead of on my slow server.
**
Or, you can download programs or source from my home page:
http://www.rsok.com/~jrm/.
If you only want the
first 100 primes,
they are at
http://www.rsok.com/~jrm/first100primes.html.
http://www.rsok.com/~jrm/next_ten_primes.html will print the next 10
primes after the integer you supply. If the graphics window is too small to
hold the results, please check the JAVA console window.

A sieve was used to generate a list of prime numbers. In order to reduce storage requirements, the information about prime or not prime was stored for 30 integers in each byte. Only one bit is needed to store prime or not prime for an integer. The value of the integer is known by the location of the bit.

In each 30 integers, for N >= 1, the numbers that might be prime are

N*30+1,

N*30+7,

N*30+11,

N*30+13,

N*30+17,

N*30+19,

N*30+23,

N*30+29

This means that information about prime or not prime only needs to
occupy 8 bits. A ten byte file would hold prime or not prime for 300
integers. It works because N*30 has 2,3,5 as factors, no matter what
the value of N. (N*30)+3 has 3 as a factor since 3 is also a factor
of 30. (N*30)+(x*3) also has 3 as a factor since it could be written
as (N*10 + x)*3.

The relationship used for this compact storage of prime numbers might be described by:

(2-1)*(3-1)*(5-1) ----------------- == 8 bits / 30 integers 2*3*5

In a traditional sieve, one bit is used to store prime or not prime for each integer. If one knows that the only even prime is 2 and stores that information in the algorithm instead of in memory, then 1/2 as much memory is needed. Using the notation above,

(2-1)/2 == 1 bit / 2 integers

By not storing 3, then

((2-1)*(3-1))/(2*3) == 2 bits / 6 integers

of the storage is required, (or, 1/3 as much storage as was required when one used a bit for each integer) but that is not as convenient for storage at 8 bits/byte.

My 8 bits for thirty integers storage scheme could be extended to:

(2-1)*(3-1)*(5-1)*(7-1) ----------------------- == 48 bits / 210 integers 2*3*5*7

which would be 6/7 of storage requirement of the method that I used. If extended to the next prime, then only 10/11 as much storage would be used, or 60/77 as much storage as I used.

Enter two positive integers in the form below to get a list of prime numbers in the interval. I suggest not doing too large a range to avoid running your web browser out of memory. If you want all 98 million primes less than 2000000000, then I suggest downloading my sieve program. There are links to source code and binaries below. The sieve program will run much faster than this slow web server can deliver the numbers to your browser. For example, my old 300 MHz AMD K6 took 1 hour and 33 minutes just to print the 367783654 primes less than 8000000000. If you want just a few hundred primes, this web server will be fairly quick and it has all of the primes less than 8000000000. I have done a Windows version of the sieve program that will go to 8000000000, or maybe further if you have enough ram. The 64 bit program is called sieve2310_64bit.exe. If you want this for Linux, all that is needed is to change the unsigned longs into long longs and change the printf formats and compile with gcc 3.2 (or newer) or any C99 compliant compiler. sieve2310_64bit.c

Please limit yourself to a range of about 100000 to avoid connection timeouts. If you want more, download the program as mentioned above.

More information about prime numbers from the University of Tennessee at Martin.

More information about prime numbers from the University of Utah.

An explanation of what prime numbers are from dr.math.

Prime numbers as a sequence of integers at www.research.att.com.

**http://dmoz.org/Science/Math/Number_Theory/Prime_Numbers/** has many
good links to web pages about prime numbers.

Source code for a sieve program from a web server, or embedded in html for easy viewing with Internet Explorer sieve2310.c.html or ftp sieve2310.c or to ftp a 32bit ".EXE" file and source for Microsoft Windows sieve2310.exe

This program which uses (with permission) a small amount of my code calculates various prime number statistics. http://ndirty.cute.fi/~karttu/matikka/Schemuli/primestats.c.txt.

Find the
next prime number larger than an integer you provide. This
is a JAVA program and requires a new enough JAVA in your web browser
to include the java.math.BigInteger package. Source code is
here.

Find the
next ten prime numbers after the integer you provide.

factor.exe is a Windows NT commmand line program to print the prime factors of an integer. It may also work with Windows 98. Type "factor help" to get a usage message. It seems to work on integers up to about 9007199254740989. bfactor.exe is another Windows NT command line program to print the prime factors of an integer. It will attempt to factor integers up to about 600 digits, but most will take a very long time, maybe many years. If the Windows 98 command line is not long enough, bfactor will read one integer per line from stdin. 31610054640417607788145206291543662493274686990 is an easy integer for bfactor.exe to factor if you want to test it without waiting too long. There is also a Linux binary of bfactor.

John Moyer's home page

send email to John Moyer

If you were wanting all of the prime numbers instead of just those up to some arbitrary limit, then you are out of luck. There are an infinite number of primes. A greek named Euclid proved this a couple thousand years ago. He proved this by assuming that there were a finite number of primes and prime N was the biggest prime. Then, one could multiply all of the primes together and add one to the product. This new number is not divisible by any of the primes that were multiplied together, therefore it is either a prime itself, or it is a product of a prime larger than the one we earlier assumed to be the largest prime. So the assumption was false and there is no largest prime. You cannot get all of the prime numbers. There is always a bigger prime.

If you use each of those digits exactly once, then you cannot arrange them as a prime. The sum of those nine digits is 45 which is divisible by 3. Therefore, 3 is a factor of any of those nine digit numbers and none of them are prime.

The reason why this works is that the 9 digit number may be written as a polynomial. To illustrate this with a 3 digit number, 456 may be written as 4*10*10+5*10+6. Then, since 10=(9+1) it may also be written as 4*(9+1)*(9+1)+5*(9+1)+6. For an arbitrary 3 digit number where the digits are represented by a, b, c, it would be a*(9+1)*(9+1)+b*(9+1)+c. This may be multiplied out to be (a*9+a*1)*(9+1)+b*(9+1)+c. Multiplying one more time we get ((a*9)*9+(a*1)*9+(a*9)*1+(a*1)*1)+b*9+b*1+c. This simplifies to a*81+a*9+a*9+a+b*9+b+c. Since 3 evenly divides each of the terms that contain a 9 or a multiple of 9, then if 3 evenly divides the remaining terms (a+b+c) the entire number is evenly divisible by 3.

Copyright © 1999-2007, John Moyer, All rights reserved.