• 登录

求C#找质数以及合数算法!!!

算法 C#

lastfm - 1年前

• 
  admin - 1年前

  在网上看到很多找质数的算法，都是检查从2到n-1的数能否被n整除，能就不是质数，反之就是素数，这样做当然是正确的，但是浪费了一些没有必要的检查， 其实只要检查从2到sqrt（n）之间的数就可以了，因为如果一个数有因子的话，那么它必定有一个因子不大于该数的平方根。
  

          public static void PrimeNum(int maxNum)
          {
              for (int i = 3; i <= maxNum; i++)
              {
                  bool IsPrime = true;
                  for (int j = 2; j <= Math.Sqrt(i); j++)
                  {
                      if (i % j == 0)
                      {
                          IsPrime = false;
                          break;//有因子证明是合数，马上退出循环。
                      }
                  }
                  if (IsPrime)
                  {
                      Console.Write(i.ToString()+" ");
                  }
              }
          }