C#找质数（素数）

    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;
    using System.Diagnostics;
    
    namespace ConAppPrimeNumber
    {
    
    class Program
    {
        static void Main(string[] args)
        {
    
            System.Diagnostics.Stopwatch s = new Stopwatch();
    
            //s.Start();
            //PrimeNumber.Find3();
            //s.Stop();
            //System.Console.WriteLine("Watch Time:{0}m, {1}s, {2}ms", s.Elapsed.Minutes, s.Elapsed.Seconds, s.ElapsedMilliseconds);
    
            //System.Console.WriteLine();
    
            s.Reset();
            s.Start();
            PrimeNumber.Find4();
            s.Stop();
            System.Console.WriteLine("Watch Time:{0}m, {1}s, {2}ms", s.Elapsed.Minutes, s.Elapsed.Seconds, s.ElapsedMilliseconds);
    
        }
    }
    
    
    public class PrimeNumber
    {
        static int n = 100000;      //查找10w(n=10w)以内的素数    
        //static int n = 1000000;   //100w    
        static bool IsPN = false;   //找到素数就设置为true
        static int count = 0;       //计数器
    
        //找奇数
        public static void Find()
        {
            for (int i = 1; i < n; i++)
            {
                if (i % 2 == 0) continue;//先过滤能被2整除的数，%表示取模，类似delphi中的Mod
                System.Console.Write(i + "\t");
            }
        }
    
        //找奇数，优化代码
        public static void Find2()
        {
            for (int i = 1; i < n; i = i + 2)//通过循环步进值得到奇数
            {
                System.Console.Write(i + "\t");
            }
        }
    
        //找质数（只能被1和本身整除的数就是质数），质数同时也叫素数//查询找10W以内的，需要1秒
        public static void Find3()
        {
            IsPN = false;
            System.Console.Write(2 + "\t" + 3 + "\t");//因为下面优化代码，所以2和3必须在这里输出
            count = 2;
    
            for (int i = 1; i < n; i += 2)//先找出1，3，5，7，9。。。奇数
            {
                for (int j = 3; j < i; j += 2)//从3开始，比如3，5，7。。。，把1，2，4，6。。。去掉
                {
                    if (i % j == 0)
                    {
                        IsPN = false;//不是质数
                        break;
                    }
                    IsPN = true;
                }
                if (IsPN)
                {
                    System.Console.Write(i + "\t");   //需要看Watch，请注释此语句
                    count++;
                }
            }
            System.Console.WriteLine("Count: {0}", count);
        }
    
        //找质数，优化代码//查找1000W以内6秒
        public static void Find4()
        {
            IsPN = false;
            System.Console.Write(2 + "\t" + 3 + "\t");
            count = 2;
    
            for (int i = 1; i < n; i += 2)
            {
                for (int j = 3; j < i; j += 2)
                {
                    if (i % j == 0)
                    {
                        IsPN = false;
                        break;
                    }
    
                    //被除数的平方大于这个数则不必判断，拿97来说，当除以3/5/7/9/11之后还有余数，后面的13/15/17，其实是没必要再验证了，因为11*11已经大于97
                    //这里本是要对i开平方根，i % j==0，j的取值范围是小于i的平方根以内的所有素数，因为不好实现，所以我改用质数的平方
                    if (j * j > i)
                    {
                        IsPN = true;
                        break;
                    }
                }
    
                if (IsPN)
                {
                    System.Console.Write(i + "\t");   //需要看Watch，请注释此语句
                    count++;
                }
            }
            System.Console.WriteLine("Count: {0}", count);
        }        
    
    }
    }