# Some Prime Numbers This page is sponsored by https://www.A-Wee-Bit-of-Ireland.com/. https://www.A-Wee-Bit-of-Ireland.com/ has photos made in Ireland. More photos made by John Moyer may be found at https://www.rsok.com/~jrm/photos/index.html.

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: https://www.rsok.com/~jrm/. If you only want the first 100 primes, they are at https://www.rsok.com/~jrm/first100primes.html. https://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.

### The ending integer

Source code for a sieve program from a web server, or embedded in html for easy viewing with Internet Explorer sieve2310.c.html

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.