Simple primality test in CSharp

By Oct 20, 2016

Description:

Simple primality test in CSharp

Preferencesoft

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.

 


CSharp

Categories

Share

Follow


KodFor Privacy Policy