c# - 在小于N的质数中，找到一个数字，该基本数字在2个基本系统中包含最大数量的1-s。

Closed. This question is off-topic. It is not currently accepting answers. Learn more。
想改进这个问题吗Update the question所以堆栈溢出的值小于aa>。
我的问题是：
我想找到一个小于N的质数，在2基数系统中对应的数包含最大数。
例如，对于N = 87我的程序返回了31（在2个基本系统中为11111）。
我正在寻找更好的解决办法来解决这个问题。
我的算法如下：

static int Slow(int N)
{
    int maxCount = 0;
    int maxi = 5;

    for (int i = 5; i <= N; i+=2)
    {
        if (Isprime(i))
        {
           string x = ConvertToPBase(i, 2);
           int count = Count1In(x);
           if (count > maxCount)
           {
              maxCount = count;
              maxi = i;
           }
       }
    }

    return maxi;
}

我的IsPrime方法如下：

static bool Isprime(int n)
{
    if (n == 2)
       return true;
    if (n == 3)
       return true;
    if (n % 2 == 0)
       return false;
    if (n % 3 == 0)
       return false;

    int i = 5;
    int w = 2;

    while (i * i <= n)
    {
        if (n % i == 0)
            return false;

        i += w;
        w = 6 - w;
    }

    return true;
}

我的ConvertToPBase方法如下：

static string ConvertToPBase(int numberInTenBase, int P)
{
    List<int> list = new List<int>();
    while (numberInTenBase > 0)
    {
        list.Add((numberInTenBase % P));
        numberInTenBase /= P;
    }

    list.Reverse();
    string x = "";
    foreach (var item in list)
    {
        x += item;
    }
    return x;
}

我的count1方法如下：

static int Count1In(string x)
{
    int count = 0;

    for (int i = 0; i < x.Length; i++)
    {
        if (Convert.ToInt32(x[i].ToString()) == 1)
            count++;
    }

    return count;
}

最佳答案

如果对输入值有限制（值为int因而value <= int.MaxValue）
我建议解决所有可能的位集（1..30）的问题，并将解决方案放入一个集合中，即。

            | min prime composed
   bits set |   binary | decimal
  -------------------------------
         1  |       10 |       2
         2  |       11 |       3
         3  |      111 |       7
         4  |    10111 |      23
         5  |    11111 |      31
       ...

完成此操作后，您可以轻松地将解决方案实现为

   private static Dictionary<int, int> s_Solutions = new Dictionary<int, int>() {
     {0, int.MinValue},
     {1, 2},
     {2, 3},
     {3, 7},
     {4, 23},
     {5, 31},
     ...
   };

   // O(1) solution - 31 items to scan only for the arbitrary N
   static int NotThatSlow(int N) {
     return s_Solutions
       .Where(pair => pair.Value < N)
       .OrderByDescending(pair => pair.Key)
       .Select(pair => pair.Value)
       .First();
   }