当前位置：首页 > article >正文

C#，纽曼-尚克斯-威廉士素数（Newman Shanks Williams prime）的算法与源代码

article 2025/1/17 0:02:53

1 NSW素数

素数是纽曼-尚克斯-威廉士素数（Newman-Shanks-Williams prime，简写为NSW素数）当且仅当它能写成以下的形式：

1981年M. Newman、D. Shanks和H. C. Williams在研究有限集合时，率先描述了NSW素数。

首几个NSW素数为7,41, 239, 9369319, 63018038201, ...，对应指数3, 5, 7, 19, 29, ...

上式中的S可用递归的方法定义，虽然得出来的未必是素数：

S0 = 1S1 = 1Sn = 2Sn - 1 + Sn - 2对于所有这个数列的首几项为1, 1, 3, 7,17, 41,99。这些数亦出现在以连分数表示的√2。

计算结果：

计算纽曼-尚克斯-威廉士素数的源程序（内含三种算法）：

2 文本格式源程序

using System;

namespace Legalsoft.Truffer.Algorithm
{
   public static partial class Number_Sequence
   {
       public static int Newman_Shanks_Williams_Prime(int n)
       {
           if (n == 0 || n == 1)
           {
               return 1;
           }
           return (2 * Newman_Shanks_Williams_Prime(n - 1) + Newman_Shanks_Williams_Prime(n - 2));
       }

       public static int Newman_Shanks_Williams_Prime_Second(int n)
       {
           int[] dp = new int[n + 1];
           dp[0] = dp[1] = 1;
           for (int i = 2; i <= n; i++)
           {
               dp[i] = 2 * dp[i - 1] + dp[i - 2];
           }
           return dp[n];
       }

       public static int Newman_Shanks_Williams_Prime_Third(int n)
       {
           if (n == 0 || n == 1)
           {
               return 1;
           }
           int a = 1;
           int b = 1;
           for (int i = 2; i <= n; ++i)
           {
               int c = 2 * b + a;
               a = b;
               b = c;
           }
           return b;
       }
   }
}

————————————————————

POWER BY TRUFFER.CN 50018.COM

3 代码格式

using System;

namespace Legalsoft.Truffer.Algorithm
{
    public static partial class Number_Sequence
    {
        public static int Newman_Shanks_Williams_Prime(int n)
        {
            if (n == 0 || n == 1)
            {
                return 1;
            }
            return (2 * Newman_Shanks_Williams_Prime(n - 1) + Newman_Shanks_Williams_Prime(n - 2));
        }

        public static int Newman_Shanks_Williams_Prime_Second(int n)
        {
            int[] dp = new int[n + 1];
            dp[0] = dp[1] = 1;
            for (int i = 2; i <= n; i++)
            {
                dp[i] = 2 * dp[i - 1] + dp[i - 2];
            }
            return dp[n];
        }

        public static int Newman_Shanks_Williams_Prime_Third(int n)
        {
            if (n == 0 || n == 1)
            {
                return 1;
            }
            int a = 1;
            int b = 1;
            for (int i = 2; i <= n; ++i)
            {
                int c = 2 * b + a;
                a = b;
                b = c;
            }
            return b;
        }
    }
}

查看全文

http://www.kler.cn/a/229303.html