C#编程实现判断素数的方法_c#判断素数

第一种方法，根据素数的定义判断，代码如下：

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Numerics;
 
namespace fastPrim
{
    class Program
    {
        /// <summary>
        /// 判断素数
        /// </summary>
        /// <param name="num"></param>
        /// <returns></returns>
        static bool isPrim(int num)
        {
            for(int i=2;i<num-1;i++)
            {
                if (num % i == 0)
                {                    
                    return false;
                }
            }
            Console.WriteLine(num.ToString() + "是素数");
            return true;
        }
        static void Main(string[] args)
        {
            //判断100以内的素数
            int n = 100;
            for (int i = 2; i < n+1; i++)
            {
                isPrim(i);
            }
 
            Console.Read();
        }
    }
}

根据素数的定义，即素数是只能被1和本身整除的数字，上面的isPrim函数就是根据这点进行编码实现的。

第二种方法，是对第一种判断素数方法的优化，原理是：如果一个数n不能被i整除，那他也不能被n/i整除，所以我们只需要判断n能不能被自己的平方根以内的数整除即可。

/// <summary>
        /// 判断素数的改良方法
        /// </summary>
        /// <param name="num"></param>
        /// <returns></returns>
        static bool isPrimFast(int num)
        {
            for (int i = 2; i <= Math.Sqrt(num); i++)
            {
                if (num % i == 0)
                {
                    return false;
                }
            }
            Console.WriteLine(num.ToString() + "是素数");
            return true;
        }

从上面的代码可以看出，第一种判断素数方法是线性时间复杂度，而第二种方法是平方根时间复杂度，比较节省时间。