Prime Number Algorithm

Introduction

The algorithm for calculating prime numbers is based on the idea of ​​a prime number as the movement of such numbers. The basic idea is that prime numbers starting with 5 are not static, but dynamic, and can only appear in strictly defined places (6n ± 1). Thus, each new prime number, appearing, begins to move and occupy these places, preventing new prime numbers from appearing, since they will be derivatives of another prime number. To calculate the free space for the new estimated primes, which are formed by adding 2 and 4 to the initial one (5) in turn, division with the remainder is used for all previously stored primes, and if at least once the remainder is 0, then the place is taken, otherwise it is a new prime. Thus, the algorithm shows that primes do not appear randomly, but can be calculated from the previous ones.

Background

More details about the nature of primes can be found in my research Prime Number Explanation. Sorry for the quality, no degree, did by hand.

Using the Code

The code can be copied and pasted into the main method, to get the desired number of primes, change the cycle limit and run it.

/* The flag indicates whether free space is available for the new prime.
 */
bool free;

/* Every prime number after 5 has its own factor. For example, 5 represents
 * a number of the form 6*1-1, its factor is -1, the next, if not occupied,
 * will have a factor of +1, then again -1, and so on.
 */
int factor = -1;

/* A collection of prime numbers.
 */
var primes = new List<uint>();

/* Start with 5, as this is the first dynamic prime.
 */
primes.Add(5);

/* Estimated next prime.
 */
uint next = primes.First();

for (int i = 0; i < 5000000; i++)
{
   /* Beginning with the assumption that the place is free.
    */
   free = true;

   /* Add to the estimated next number 2 or 4, depending on the factor.
    * If the factor is -1, like 5, then the next possible number is in 2 
    * and has a factor of +1, and the next is already in 4 with a factor of -1, and so on.
    */
   next += factor < 0 ? 2U : 4U;

   /* Go through the found primes, starting with the first.
    */
   foreach(var p in primes)
   {
       /* Only get to the middle, since then the remainder will never be 0.
        */
       if (next - p < p) break;
       
       /* If such a number is found, dividing by which the remainder is 0,
        * then the current estimated prime number is derived from it, therefore, is not prime.
        */
       if (next % p == 0) { free = false; break; }
   }

   /* If there was not a single division with a remainder of 0, 
    * then the current estimated number is prime, and is added to those found.
    */
   if (free) primes.Add(next);

   /* Change the factor. If there was a minus, it will become a plus, and vice versa.
    */
   factor -= 2 * factor;
}

/* Output
 */
Console.WriteLine("The last prime: " + primes.Last());
Console.WriteLine("The count of primes: " + primes.Count());

Console.ReadKey();

The opposite way of finding primes, the more reflective the idea, but extremely inefficient. In contrast to the previous one, it moves forward on a numerical line, as if running into the future. The found prime (6n±1) is extended by calculating all the numbers that will be at 6n±1 positions. These numbers are placed in the set, so only 6n±1 numbers will be in it, other numbers do not matter, because they will always be divisible by 2 or 3. The next 6n±1 number after the largest found prime is checked for presence in the set, and if it is there, then it is composite, otherwise it is prime.

var composites = new HashSet<uint>();
var primes = new List<uint>();
int factor = -1;
uint next = 5;
int limit = 1000;

while(next < limit)
{
    /* If the next is not in the set, then it is prime,
     * and it is necessary to calculate its future positions on 6n±1.
     * Example. We have 5 (6*1-1), its next positions are 
     * 5+5*4=25 (6*4+1), 25+5*2=35 (6*6-1), 35+5*4=55 (6*9+1)and so on to the limit. 
     * The next number for 5 (6*1-1) goes 7 (6*1+1),it is not in the set, 
     * so it is added, and its future positions go to the set,
     * 7 (6*1+1), 7+7*4=35 (6*6-1), 35+7*2=49 (6*8+1) and so on.
     */
    if (! composites.Contains(next))
    {
        uint temp = next;

        /* Go to the limit.
         */
        while (temp < limit)
        {
            /* Get and add the next 6n±1 position of the prime.
             */
            temp += next * 4;
            composites.Add(temp);

            /* Get and add the next 6n±1 position of the prime.
             */
            temp += next * 2;
            composites.Add(temp);
        }

        primes.Add(next);
    }

    /* Get the next 6n±1 number (estimated prime).
     */
    next += factor < 0 ? 2U : 4U;
    factor -= 2 * factor;
}

Points of Interest

In general, it is very funny, it is like a road along which prime numbers move discretely. And the new number needs to cross this road, as it were, and do it only in a strictly designated place, and if possible immediately after the largest number, so that it does not collide with others. And as soon as this transition is found, the number occupies it, the road becomes wider, and the traffic is more intense than making the transition more difficult.

These ways are ineffective and have rather theoretical interest.

History

• 17^th October, 2019: Initial version
• 21^st October, 2019: Second version (added the opposite way; omitted the efficiency question)