# Simple primality test in CSharp

## Basic primality test

A basic algorithm for determining whether
an integer is prime or not is to check that the integer is divisible by any
integer between 2 and *n*-1.

But it may be limited to integers between 2 and , because if it was divisible by an integer then it would be divisible by the integer .

As in article Primality test, may also be removed from the beginning integer divisible by two and three.

We will start with a first program that eliminates
an integer when it is divisible by 2, 3 and 5.

It limits the divisibility tests for other integers.

Divisibility by 2, 3 and 5 is repeated by period 2.3.5 = 30

0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |

10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |

20 |
21 |
22 |
23 |
24 |
25 |
26 |
27 |
28 |
29 |

30 |
31 |
32 |
33 |
34 |
35 |
36 |
37 |
38 |
39 |

40 |
41 |
42 |
43 |
44 |
45 |
46 |
47 |
48 |
49 |

50 |
51 |
52 |
53 |
54 |
55 |
56 |
57 |
58 |
9 |

• Multiples of 5 are shown in green,

• multiples of 3, not multiples of 5 are shown in pink,

• multiples of 2 remaining are shown in blue.

Here is the program:

```
static bool IsPrime(int n)
{
int[] dep = new int[] { 4, 2, 4, 2, 4, 6, 2, 6 };
switch (n)
{
case 0:
case 1:
case 4:
return false;
case 2:
case 3:
case 5:
return true;
}
if (n % 2 == 0)
return false;
if (n % 3 == 0)
return false;
if (n % 5 == 0)
return false;
int i = 7;
int j = 0;
while (i * i <= n)
{
if (n % i == 0)
return false;
i = i + dep[j];
j = ++j % 8;
}
return true;
}
```

## Using Tables

For the 32-bits or 64-bits integers, sophisticated primality tests are not generally used. But we can save time by using prime numbers table and a table to browse integers not divisible by 2,3,5,7,11, …

For generating tables:

```
static void GeneratePrimeTable(int fromP = 2, int n = 500)
{
int j = 0;
int i = fromP;
StringBuilder sb = new StringBuilder("int[] primeTable={", n);
while (j < n)
{
if (IsPrimeC(i))
{
if (j % 10 == 0)
sb.Append("\n");
if (j == n - 1)
sb.Append(string.Format("{0}", i));
else
sb.Append(string.Format("{0},", i));
j++;
}
i++;
}
sb.Append("\n};");
Console.WriteLine(sb.ToString());
}
static void GenerateDivisibilityTable(int p = 11, int fromP = 7)
{
//p prime number < 100
//fromP must not be divisible by 2, ..., p
int[] prime = new int[25] {
2,3,5,7,11,13,17,19,23,29,
31,37,41,43,47,53,59,61,67,71,
73,79,83,89,97};
int n = 1;
for (int i = 0; i < 25; i++)
if (prime[i] <= p)
n *= prime[i];
int[] divisible = new int[n + 1];
for (int k = 0; k < n + 1; k++)
divisible[k] = k;
for (int a = 0; a < n + 1; a++)
{
bool condition = false;
for (int i = 0; i < 25; i++)
if (prime[i] <= p)
condition = condition || ((fromP + a) % prime[i] == 0);
if (condition)
divisible[a] = -1;
}
//calculating deplacements from fromP
List<int> listDep = new List<int>();
int acc = 0;
for (int a = 0; a < n + 1; a++)
if (divisible[a] != -1)
{
listDep.Add(divisible[a] - acc);
acc = divisible[a];
}
int ne = listDep.Count;
StringBuilder sb = new StringBuilder("int[] dep={", ne);
for (int i = 0; i < ne; i++)
{
if (i % 10 == 0)
sb.Append("\n");
if (i == ne - 1)
sb.Append(string.Format("{0}", listDep[i]));
else
sb.Append(string.Format("{0},", listDep[i]));
}
sb.Append("\n};");
Console.WriteLine(sb.ToString());
}
```

The program :

```
static bool IsPrime(int n)
{
//505 prime numbers
//GeneratePrimeTable(2, 505);
int[] primeTable = {
2,3,5,7,11,13,17,19,23,29,
31,37,41,43,47,53,59,61,67,71,
73,79,83,89,97,101,103,107,109,113,
127,131,137,139,149,151,157,163,167,173,
179,181,191,193,197,199,211,223,227,229,
233,239,241,251,257,263,269,271,277,281,
283,293,307,311,313,317,331,337,347,349,
353,359,367,373,379,383,389,397,401,409,
419,421,431,433,439,443,449,457,461,463,
467,479,487,491,499,503,509,521,523,541,
547,557,563,569,571,577,587,593,599,601,
607,613,617,619,631,641,643,647,653,659,
661,673,677,683,691,701,709,719,727,733,
739,743,751,757,761,769,773,787,797,809,
811,821,823,827,829,839,853,857,859,863,
877,881,883,887,907,911,919,929,937,941,
947,953,967,971,977,983,991,997,1009,1013,
1019,1021,1031,1033,1039,1049,1051,1061,1063,1069,
1087,1091,1093,1097,1103,1109,1117,1123,1129,1151,
1153,1163,1171,1181,1187,1193,1201,1213,1217,1223,
1229,1231,1237,1249,1259,1277,1279,1283,1289,1291,
1297,1301,1303,1307,1319,1321,1327,1361,1367,1373,
1381,1399,1409,1423,1427,1429,1433,1439,1447,1451,
1453,1459,1471,1481,1483,1487,1489,1493,1499,1511,
1523,1531,1543,1549,1553,1559,1567,1571,1579,1583,
1597,1601,1607,1609,1613,1619,1621,1627,1637,1657,
1663,1667,1669,1693,1697,1699,1709,1721,1723,1733,
1741,1747,1753,1759,1777,1783,1787,1789,1801,1811,
1823,1831,1847,1861,1867,1871,1873,1877,1879,1889,
1901,1907,1913,1931,1933,1949,1951,1973,1979,1987,
1993,1997,1999,2003,2011,2017,2027,2029,2039,2053,
2063,2069,2081,2083,2087,2089,2099,2111,2113,2129,
2131,2137,2141,2143,2153,2161,2179,2203,2207,2213,
2221,2237,2239,2243,2251,2267,2269,2273,2281,2287,
2293,2297,2309,2311,2333,2339,2341,2347,2351,2357,
2371,2377,2381,2383,2389,2393,2399,2411,2417,2423,
2437,2441,2447,2459,2467,2473,2477,2503,2521,2531,
2539,2543,2549,2551,2557,2579,2591,2593,2609,2617,
2621,2633,2647,2657,2659,2663,2671,2677,2683,2687,
2689,2693,2699,2707,2711,2713,2719,2729,2731,2741,
2749,2753,2767,2777,2789,2791,2797,2801,2803,2819,
2833,2837,2843,2851,2857,2861,2879,2887,2897,2903,
2909,2917,2927,2939,2953,2957,2963,2969,2971,2999,
3001,3011,3019,3023,3037,3041,3049,3061,3067,3079,
3083,3089,3109,3119,3121,3137,3163,3167,3169,3181,
3187,3191,3203,3209,3217,3221,3229,3251,3253,3257,
3259,3271,3299,3301,3307,3313,3319,3323,3329,3331,
3343,3347,3359,3361,3371,3373,3389,3391,3407,3413,
3433,3449,3457,3461,3463,3467,3469,3491,3499,3511,
3517,3527,3529,3533,3539,3541,3547,3557,3559,3571,
3581,3583,3593,3607,3613
};
// GenerateDivisibilityTable(11, 3613);
// 3613 is successor of 3607
int[] dep ={
0,4,6,6,2,6,6,6,4,6,
8,4,2,4,2,4,8,6,4,8,
4,6,2,6,6,4,2,4,6,8,
4,2,4,2,10,2,10,2,4,2,
4,6,2,10,2,4,6,8,6,4,
2,6,4,6,8,4,6,2,4,8,
6,4,6,2,4,6,2,6,6,4,
6,6,2,6,6,4,2,10,2,10,
2,4,2,4,6,2,6,4,2,10,
6,2,6,4,2,6,4,6,8,4,
2,4,2,12,6,4,6,2,4,6,
2,12,4,2,4,8,6,4,2,4,
2,10,2,10,6,2,4,6,2,6,
4,2,4,6,6,2,6,4,2,10,
6,8,6,4,2,4,8,6,4,6,
2,4,6,2,6,6,6,4,6,2,
6,4,2,4,2,10,12,2,4,2,
10,2,6,4,2,4,6,6,2,10,
2,6,4,14,4,2,4,2,4,8,
6,4,6,2,4,6,2,6,6,4,
2,4,6,2,6,4,2,4,12,2,
12,4,2,4,6,2,6,4,2,4,
6,6,2,6,4,2,6,4,6,8,
4,2,4,2,4,14,4,6,2,10,
2,6,6,4,2,4,6,2,10,2,
4,2,12,10,2,4,2,4,6,2,
6,4,6,6,6,2,6,4,2,6,
4,6,8,4,2,4,6,8,6,10,
2,4,6,2,6,6,4,2,4,6,
2,6,4,2,6,10,2,10,2,4,
2,4,6,8,4,2,4,12,2,6,
4,2,6,4,6,12,2,4,2,4,
8,6,4,6,2,4,6,2,6,10,
2,4,6,2,6,4,2,4,2,10,
2,10,2,4,6,6,2,6,6,4,
6,6,2,6,4,2,6,4,6,8,
4,2,6,4,8,6,4,6,2,4,
6,8,6,4,2,10,2,6,4,2,
4,2,10,2,10,2,4,2,4,8,
6,4,2,4,6,6,2,6,4,8,
4,6,8,4,2,4,2,4,8,6,
4,6,6,6,2,6,6,4,2,4,
6,2,6,4,2,4,2,10,2,10,
2,6,4,6,2,6,4,2,4,6,
6,8,4,2,6,10,8,4,2,4,
2,4,8,10,6,2,4,8,6,6,
4,2,4,6,2,6,4,6,2,10,
2,10,2,4,2,4,6,2,6,4,
2
};
int a = dep.Length;
if (n <= 3607)
if (Array.IndexOf(primeTable, n) < 0)
return false;
else
return true;
else
{
int i = 2;
int j = 0;
while (i * i <= n && j < 504)
{
if (n % i == 0)
return false;
++j;
i = primeTable[j];
}
if (j < 504)
return true;
i = 3613;
j = 0;
while (i * i <= n)
{
if (n % i == 0)
return false;
i = i + dep[j];
j = ++j % 481; //481 is dep.Length
}
return true;
}
}
```

## Using a regular expression

This primality test uses nothing but a regular expression and does not rely on the usual arithmetic operations.

But the fact that the integer is developed in base 1, the test is not at all effective for large integers. You will find at this address:

a-regular-expression-to-check-for-prime-numbers

detailed explanations of the regular expression.

Here is the C# program:

```
static bool ReIsPrime(int n)
{
Regex re = new Regex(@"^1?$|^(11+?)\1+$");
string s = new string('1', n);
return !re.IsMatch(s);
}
```

Let us now give a further explanation on the principle:

Let *n* an integer .

Repeat 1, *n* times to obtain a chain
of 1.

If *n* = 0 then the expression is
empty;

If *n* = 1, we get 1

If *n* = 2, we get 11

…

In other words, we write the integer *n*
in base 1 (with a single digit)

The first condition of the regular expression eliminates 0 and 1, that are not prime numbers.

The rest of the regular expression, try to make a package of at least two consecutive 1 early in the chain, which can be repeated until the end of the chain. If successful, the number is a composite number, as equal to the number of packages multiplied by the common number of 1 contained therein.