C# 判断质数的2种基本方法

质数（prime number）又称，有无限个。

质数定义为在大于1的自然数中，除了1和它本身以外不再有其他。

目前学习了判断数字n是否为质数的2种基本方法：

一、计数法

根据定义，既然质数只能够被1和他本身整除。我们可以统计出1到n范围内的整数，能够整除n的个数。再判断这个个数是否等于2就可以知道n是不是质数。

代码如下：

            int n = int.Parse(Console.ReadLine()); ;
            int sum = 0;
            for (int i = 1; i <= n; i++)
            {
                if (n % i == 0)
                {
                    sum += 1;
                }
            }
            if (sum == 2)
            {
                Console.WriteLine("n是质数");
            }
            else
            {
                Console.WriteLine("n不是质数");
            }

二、查找法

可以查找2 到n-1范围内所有的数去除n，如果能够整除，这表明这个数不是质数。

代码如下：

            int n = int.Parse(Console.ReadLine()); ;
            bool isFind = false;
            for (int i = 2; i <= n - 1; i++)
            {
                if (n % i == 0)
                {
                    isFind = true;
                    break;
                }
            }
            if (!isFind)
            {
                Console.WriteLine("n是质数");
            }
            else
            {
                Console.WriteLine("n不是质数");
            }

思考：

计数法需要判断1到n范围内的所有整数是够能整除n，如果n的值比较大相应的计算量就较大。

查找法一旦找到2到n-1范围内第一个能够整除n的数就会跳出循环，但是如果要判断出质数也要所有的都除一遍都不能整除才能得出是质数的结论，如果n的值比较大也同样会面对计算量就较大的问题。

如果一个程序中有多次判断质数，再在这些结论的基础上运行下一步程序，整个程序运行速度就会慢。比如哥赫巴德猜想（任何大于2的偶数都可以分解成2个质数的和）中如果输入的数为7位数或8位数，程序明显会慢很多才能运行完。

总的来说，计算机只能按照设定的程序来执行，算法需要人来优化。