15,793,064 members
Articles / Programming Languages / C#
Tip/Trick

# Prime Number Algorithm

Rate me:
18 Oct 2019MIT2 min read 18.3K   7   24
Algorithm for calculating primes based on research on primes

## 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.

C#
```/* 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>();

*/

/* 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.
*/

/* 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());

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.

C#
```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;

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

}

/* 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

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

Written By
Russian Federation
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

 First Prev Next
 How can we get in contact? Alysia Culley7-Oct-21 8:06 Alysia Culley 7-Oct-21 8:06
 Re: How can we get in contact? Sergei Lazarev7-Oct-21 8:26 Sergei Lazarev 7-Oct-21 8:26
 Dynamic Prime Numbers - An Interesting concept. Member 133717628-Feb-20 20:45 Member 13371762 8-Feb-20 20:45
 Re: Dynamic Prime Numbers - An Interesting concept. Sergei Lazarev8-Feb-20 22:38 Sergei Lazarev 8-Feb-20 22:38
 A smart way of testing for primes. George Swan23-Oct-19 23:18 George Swan 23-Oct-19 23:18
 This algorithm is an excellent and smart way of testing for primes rather than a predictor of primes. It skips testing all even numbers and the odd numbers that have 3 as a factor. When a number has been selected it has to be tested for factors. In the example below, the bracketed numbers are not selected for testing. Note that 25 is selected for testing although it is not a prime. 5(6)7(8){9}(10)11(12)13(14){15}(16)17(18)19(20){21}(22)23(24)25 ( ) even number { } odd number that's multiple of 3
 Re: A smart way of testing for primes. Sergei Lazarev24-Oct-19 0:55 Sergei Lazarev 24-Oct-19 0:55
 Five Stars for Effort Member 302712021-Oct-19 10:37 Member 3027120 21-Oct-19 10:37
 Re: Five Stars for Effort Sergei Lazarev21-Oct-19 12:08 Sergei Lazarev 21-Oct-19 12:08
 A Suggestion George Swan20-Oct-19 6:46 George Swan 20-Oct-19 6:46
 Re: A Suggestion Sergei Lazarev20-Oct-19 7:57 Sergei Lazarev 20-Oct-19 7:57
 Re: A Suggestion George Swan23-Oct-19 22:04 George Swan 23-Oct-19 22:04
 Re: A Suggestion Sergei Lazarev23-Oct-19 22:34 Sergei Lazarev 23-Oct-19 22:34
 a good try Southmountain19-Oct-19 18:59 Southmountain 19-Oct-19 18:59
 Which specific algorithm(s) is current state-of-the art for the calculation of primes larger than 9 digits? Member 1172068118-Oct-19 11:12 Member 11720681 18-Oct-19 11:12
 Re: Which specific algorithm(s) is current state-of-the art for the calculation of primes larger than 9 digits? Sergei Lazarev19-Oct-19 1:59 Sergei Lazarev 19-Oct-19 1:59
 My vote of 1 YvesDaoust18-Oct-19 2:55 YvesDaoust 18-Oct-19 2:55
 Re: My vote of 1 Sergei Lazarev18-Oct-19 3:13 Sergei Lazarev 18-Oct-19 3:13
 Re: My vote of 1 Patrice T18-Oct-19 4:36 Patrice T 18-Oct-19 4:36
 Re: My vote of 1 YvesDaoust18-Oct-19 5:04 YvesDaoust 18-Oct-19 5:04
 Re: My vote of 1 Sergei Lazarev18-Oct-19 6:00 Sergei Lazarev 18-Oct-19 6:00
 Re: My vote of 1 YvesDaoust18-Oct-19 6:38 YvesDaoust 18-Oct-19 6:38
 Re: My vote of 1 dandy7218-Oct-19 10:24 dandy72 18-Oct-19 10:24
 Use a standard Sieve YvesDaoust18-Oct-19 2:48 YvesDaoust 18-Oct-19 2:48