# Prime Number Database

Just now carried away by prime numbers. Their secret attracts me.

Wrote an algorithm similar to the sieve of Eratosthenes. For 3 hours, the program found 700 thousand first primes. And I need at least 14 million primes to multiply them to get a number with the number of decimal digits equal to 100 million pieces.

From the article “Once again about the search for prime numbers” written by a user of Bodigrim , I learned about the existence of a quick program primegen , which works using the Atkin sieve . Installed it in a LUbuntu virtual machine (VirtualBox). Indeed,

Then the question arose, how to save 14 million primes? You can simply write each prime to a file as int32. And if a prime number is more than 32-bit power?

It occurred to me to write not the numbers themselves, but the distances between them into a file. And the distance between adjacent primes should always be small, suggested that it fits in one byte.

It remains to find out the maximum possible distance for a certain range of numbers. Since the difference between primes is always an even number (except for the distance between 2 and 3), we divide the distance by 2.

In the primegen program in the source file primes.c, instead of displaying the number on the screen, I implemented an algorithm for calculating statistics on the number of distances between numbers:

Performed in the terminal:

After 10 seconds, a list is displayed:

Thus, 141 is the maximum possible prime distance of up to 1 billion.

Wrote the code to write to the file:

Launched up to 300 million:

In the file primes.bin received 16 million first primes. Compressed by the archiver 7-Zip, the file shrunk to 9 MB.

Although in our age of Gigabyte capacities, this is not very important.

Wrote an algorithm similar to the sieve of Eratosthenes. For 3 hours, the program found 700 thousand first primes. And I need at least 14 million primes to multiply them to get a number with the number of decimal digits equal to 100 million pieces.

From the article “Once again about the search for prime numbers” written by a user of Bodigrim , I learned about the existence of a quick program primegen , which works using the Atkin sieve . Installed it in a LUbuntu virtual machine (VirtualBox). Indeed,

**primegen is very fast!**Then the question arose, how to save 14 million primes? You can simply write each prime to a file as int32. And if a prime number is more than 32-bit power?

It occurred to me to write not the numbers themselves, but the distances between them into a file. And the distance between adjacent primes should always be small, suggested that it fits in one byte.

It remains to find out the maximum possible distance for a certain range of numbers. Since the difference between primes is always an even number (except for the distance between 2 and 3), we divide the distance by 2.

In the primegen program in the source file primes.c, instead of displaying the number on the screen, I implemented an algorithm for calculating statistics on the number of distances between numbers:

```
int RastCount_Index = 0;
int RastCount[1000];
for(i=0;i < 1000; i++) RastCount[i] = 0;
for (;;) {
u = primegen_next(&pg) - p;
p += u;
if (p > high) break;
for (i = 0;u;++i)
{
u += digits[i];
if (u >= 200)
{
digits[i] = u % 10;
u = u / 10;
}
else
{
digits[i] = mod10[u];
u = div10[u];
}
}
if (i > len) len = i;
int LetsRast, index;
LetsRast = 0; index = 0;
char r[40], r_old[40];
for (i = 0;i < 40; i++) { r[i] = 0; r_old[i] = 0; }
for (i = len - 1;i >= 0;--i)
{
if (! LetsRast)
if (digits_old[i] != digits[i]) LetsRast = 1;
if (LetsRast)
{
r[index] = '0' + digits[i];
r_old[index] = '0' + digits_old[i];
index++;
}
}
int ri, ri_old, Rast;
ri = atoi(r);
ri_old = atoi(r_old);
Rast = (ri - ri_old) >> 1;
RastCount[Rast]++;
if (Rast > RastCount_Index) RastCount_Index = Rast;
for (i = len-1;i >= 0; i--)
digits_old[i] = digits[i];
}
for(i = 0; i <= RastCount_Index; i++)
printf("%i = %i\n", i, RastCount[i]);
```

Performed in the terminal:

```
./primes 1 1000000000
```

After 10 seconds, a list is displayed:

0 = 1 (distance between numbers 2 and 3)

1 = 3424507

...

141 = 1

Thus, 141 is the maximum possible prime distance of up to 1 billion.

Wrote the code to write to the file:

```
FILE* fd;
fd = fopen("primes.bin", "w+");
unsigned char b1[1];
b1[0] = Rast;
fwrite(b1,1,1,fd);
fclose(fd);
```

Launched up to 300 million:

`./primes 1 300000000`

In the file primes.bin received 16 million first primes. Compressed by the archiver 7-Zip, the file shrunk to 9 MB.

**PS**There is an idea how to compress the database of primes even more strongly. It is necessary to divide the prime numbers into 4 groups according to the last decimal digit: 1, 3, 7, 9. Divide the distance between the numbers by 10. Also create 4 files. At the same time, it is possible that less than 8 bits can be allocated for distance values, but less, then it will be necessary to implement the formation of a byte buffer from, for example, 5-bit distances.Although in our age of Gigabyte capacities, this is not very important.