黑马程序员技术交流社区

标题: 关于判断一个数输入的数是否是素数，我的一点点小想法。 [打印本页]

作者: 大虾挂了 时间: 2013-9-12 22:23
标题: 关于判断一个数输入的数是否是素数，我的一点点小想法。
这里就假设用户还是很听话的，输入的是一个正整数，就不进行try，catch检查用户输入是否合法了。
最笨的方法。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication2
{
class Program
{
static void Main(string[] args)
{
int i=2;
Console.WriteLine("请输入一个正整数");
int num = Convert.ToInt32(Console.ReadLine());
for(;i<num;i++)
{
if(num%i==0)
break;
}
if (i == num)
Console.WriteLine("{0}是素数", num);
else
Console.WriteLine("{0}不是素数,可以被{1}整除",num,i); //人性化一点给出不是素数的证据
Console.ReadKey();
}
}
}

复制代码

然后想下可以优化的方法，首先我们应该不用验证那么多，一个数不可能被比它一半还大的数整除，也就是说一个数的因子不可能超过这个数的一半，其实这是对于偶数的情况，奇数的情况还可以将范围压得更小。
对于偶数，我们只要验证到它一半的那个数就可以了（咦？这种说法是不是坏掉了，偶数根本就不是质数好吧），饿。。。。所以对于偶数我们根本不用验证了。
对于奇数，想想它的最大因子可能是多少呢？设这个奇数为m，他的一个因子是n，那么m/n应该是整数（数学上的算法，不是C#中的int除以int类型结果还是int类型的那个结论）。m是固定的，什么时候n最大呢？自然是m/n最小的时候，刚才说了m是奇数，所以m/n最小值只可能是3了。最终结果，对于奇数，我们只要验证到m/3即可（这里直接用int类型算就行）

作者: 大虾挂了 时间: 2013-9-12 22:26
所以根据上面说的，可以优化代码如下

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication2
{
class Program
{
static void Main(string[] args)
{
int j = 3;
Console.WriteLine("请输入一个正整数");
int num = Convert.ToInt32(Console.ReadLine());
if (num % 2 == 0)
Console.WriteLine("{0}不是素数,可以被2整除", num);
else
{
for (; j <= num/3; j++)
{
if (num % j == 0)
break;
}
if (j == (num/3)+1)
Console.WriteLine("{0}是素数", num);
else
Console.WriteLine("{0}不是素数,可以被{1}整除", num, j); //人性化一点给出不是素数的证据
}
Console.ReadKey();
}
}
}

复制代码

作者: 大虾挂了 时间: 2013-9-12 22:56
上面的方法，对于较大的数字，计算量应该是最笨的那种的三分之一吧。
然而方法应该还可以进一步优化。验证的时候，我们没必要3,4,5,6这样挨着验证到num/3，可以3,5,7,这样隔着验证，道理很简单，因为最开始验证过2了，如果2不是这个数的因子，那么一切偶数均不是这个数的因子，所以每次循环结束j+=2就好。
这样对于比较大的数字，计算量就变为最笨那种的六分之一了吧。
对于验证一个单独的数字是否是素数，大概就这样了吧。

但是如果要求写出小于某个数字的所有素数，就有更简洁的方法了。这个更简洁的方法，是基于任何一个合数都可以化成一串素数的乘积，而得出的。
这个原理可以这样解释（上述原理理解的可以不看）：
{
如果你认为一个合数不能化成一组完全由素数组成的乘积。
我们就假设一个数字不能化成一串质数的乘积。
其中有一个数是合数，既然这个因子是合数，那么还可以将这个合数因子继续划分，如果这个合数因子能化成一些素数，那么上面结论就是成立的。如果你认为它还不能完全化为素数因子，依然有合数因子，那我们可以继续分下去。每次划分都会使得得到的合数因子变小（至少变为原来的二分之一，也就是每次划分，至少小一半）。
如果一个合数m不能化成一组质数的乘积，那么上述划分一定可以无限的进行下去才行，经过无限次划分，分出的合数因子多大呢？至少要小于等于这个数：m*（0.5）的n次方，n代表划分次数是趋于无穷大的，那么这个数是趋于0的。一个数会有0因子？显然是错误的，所以最开始假设不成立。
}

作者: 天意 时间: 2013-9-12 23:09
楼主我用2L的代码运行 2、3、5怎么处理？

作者: 天意 时间: 2013-9-12 23:23
当然，先判断一下也行，呵呵~
PS LZ应该是数学达人，看了很长时间才看懂，还有你的上一个帖子也很有研究~

作者: 大虾挂了 时间: 2013-9-12 23:55
下面写一下，要求用户输入一个整数num，程序给出不大于num的所有素数。
我想到的比较优化的代码

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication2
{
class Program
{
static void Main(string[] args)
{
int j = 3, i = 0;
Console.WriteLine("请输入一个正整数,我们将给出不大于这个数的所有素数");
int num = Convert.ToInt32(Console.ReadLine());
List<int> sushu = new List<int>();//创建一个存储素数的集合
sushu.Add(2);
for (; j <= num; j += 2)
{
for (i = 0;sushu[i]<=j/3; i++)
{
if (j % sushu[i] == 0)
break;
}
if (sushu[i] > j / 3)
sushu.Add(j);
}
foreach (int k in sushu)
{
Console.Write("{0}\t",k);
}
Console.ReadKey();
}
}
}

复制代码

实际的计算量比常规的小很多了，比如验证13是否是素数时，我们只验证了2和3两个数字（sushu集合中的前两个元素，因为13/3=4，sushu集合中，第三个元素5已经大于4了），均不是13的因子，就确定了13是一个素数。

作者: 大虾挂了 时间: 2013-9-13 00:15

天意发表于 2013-9-12 23:09
楼主我用2L的代码运行 2、3、5怎么处理？

啊，是啊，2要独立拿出来我都给忘记了，3和5嘛，把后面if判断条件的j==(num/3)+1换成j>=(num/3)+1就好了。算了，我后面贴上代码好了。

作者: 大虾挂了 时间: 2013-9-13 00:22
感谢天意君的指正，今天实在迷糊了，脑子混了，明天把代码的最终版贴出来吧。

作者: 大虾挂了 时间: 2013-9-13 01:30
果然有心事是睡不着的，最终版贴出

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication2
{
class Program
{
static void Main(string[] args)
{
int j = 3;
Console.WriteLine("请输入一个正整数");
int num = Convert.ToInt32(Console.ReadLine());
if (num == 2)
Console.WriteLine("2是素数");
else if (num % 2 == 0)
Console.WriteLine("{0}不是素数,可以被2整除", num);
else
{
for (; j <= num / 3; j += 2)
{
if (num % j == 0)
break;
}
if (j >= (num / 3) + 1) //这里选择+1很重要，+2是错误的
Console.WriteLine("{0}是素数", num);
else
Console.WriteLine("{0}不是素数,可以被{1}整除", num, j); //人性化一点给出不是素数的证据
}
Console.ReadKey();
}
}
}

复制代码

这里就是结合了我上面说的每种优化，其实最有用的就是以2为间隔验证以及验证最大因子不超过所给数字的三分之一。
这里说说程序中的这一句：
if (j >= (num / 3) + 1) //这里选择>=很重要，选择+1很重要，选择==和+2是错误的
先说为什么是>=（这里感谢天意的指正），先以2楼那个程序分析下（和这个最终优化版的区别：一个是j++，一个是j+=2），
判断是否是素数的原理是，如果是素数，循环进行了num/3+1-3，而且最后一次循环依然没有break，正常结束(最后一次j也正常加1)，j初值是3，终值是：3+num/3+1-3=num/3+1，但是这是建立在循环起码能够运行一次的前提下才有的结论，如果初始循环条件就不成立，那么j的终值其实就是初值的3。
循环进行了当输入的数字很小的时候，循环是一次都无法进行的，因为j<=num/3直接就是不成立的。所以j中存储的就是初值，循环至少进行一次的条件是num>=9。所以理论上，小于9的素数和小于9的非偶数合数都会判定失败（不过小于9的非偶数合数是不存在的），也就是输入3、5、7理论上都出错，不过巧合的是当输入7时，虽然循环没有进行，j的初值3刚好与7/3+1相等，也就是最终当输入3和5时会出错。
我们可以把3和5独立拿出来讨论，但是有更好的方法，当输入3和5时，共同点就是num/3+1=2，j的初值是3，刚好比2大，与刚才的j=num/3+1取逻辑或运算即可，也就是最终的判定条件变为j>=num/3+1。

再说这里进一步优化的方法，j+=2。
由于判定间隔了一个，所以我第一次随手也将后面改成j>=num/3+2;(程序这个位置有注释的)，这个改动各种错，首先还是那个循环一次都没进行时候的问题，如果循环一次都没有进行，那么我们就要分别看看每种情况是否正确，输入3,5,7时看下，3和5刚好取等号，而7这个时候不对了，3>=4明显是错的，所以判断7为合数了。
除了7以外的常规数字呢？当num/3刚好比你验证的最后一个数字多1时（记录此时的j=m，num/3=m+1），此次如果依然不能整除(也就是num是素数了)，此时j继续+2，也就是j=m+2，num/3+2=m+3，此时判断又出错了，所以如果判断条件是j>=num/3+1就OK了。
当j<num/3+1时，num就一定是合数么？如果因子很小的时候，这个式子必然是成立的，那么最坏的情况是什么呢？也就是验证可能是num的最大因子的那个数（num/3）,结果刚好bingo了，是num的因子，此时通过break跳出循环，所以此时虽然和num是质数的情况经过了一样的循环次数，但是却错过了j最后+2的机会，所以此时j的最终值是num/3，小于num/3+1无误。

PS：今天累翻了，话说能不能再给点技术分，~~~~(>_<)~~~~

作者: §風過無痕§ 时间: 2013-9-13 11:19
很给力0喔！我和小伙伴们都觉得赞！{:soso_e144:}

作者: 大虾挂了 时间: 2013-9-13 15:32
看了风过无痕的贴子，得知程序可以进一步优化，num/3其实是一个数最大因子的极限（最大因子不会超过num/3），也就是说，假设循环中找到因子我们也不break，我们会把这个数的所有因子都找出来。
但其实只要找到一个因子，就能说明这个数字不是素数了，所以我们需要的是那个最小因子的极限（最小因子最大不会超过多少）。如果验证到这个最小因子的极限都没有找到因子，就说明这个数不存在最小因子（当然是除了1和它本身）。存在因子即一定能找到最小（对于一个确切的合数，因子数量必然有限，这个楼上有分析），如果找不到最小因子，就说明没有因子，也就说明这个数是素数。

那这个最小因子最大不会超过多少呢？假设合数m=a*b*c*d.........何时最小的因子最大？自然是因子数目越小越好，所以最好的情况是m只能分成2个质数因子a*b。这两个数里最小的那个最大不会超过多少呢？自然是a和b相等的时候，这个最小的因子获得了它可能取得的最大值（根号m）。如果a和b不相等，必然一个大于（根号m），一个小于（根号m），此时最小因子是小于（根号m）的。

楼上说了这么多废话，只是告诉我们，验证因子的时候只需要验证到（int）（Math.sqrt(num)）即可。验证方式自然还是采取奇数偶数分别对待，偶数直接判断，奇数从3开始验证。代码

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication2
{
class Program
{
static void Main(string[] args)
{
string flag = "";
do
{
int j = 3;
Console.WriteLine("请输入一个正整数,我们将判断是否为素数");
int num = Convert.ToInt32(Console.ReadLine());
if (num == 2)
Console.WriteLine("2是素数");
else if (num % 2 == 0)
Console.WriteLine("{0}不是素数,可以被2整除", num);
else
{
for (; j <= (int)Math.Sqrt(num); j += 2)
{
if (num % j == 0)
break;
}
//当num是大于等于9素数时，循环至少进行一次，
//若(int)Math.Sqrt(num)是偶数，那么最后一次验证的j==(int)Math.Sqrt(num)-1
//循环结束时，j又加2，所以最终j==(int)Math.Sqrt(num)+1
//若(int)Math.Sqrt(num)是奇数，那么最后一次验证的j==(int)Math.Sqrt(num)
//循环结束时，j又加2，所以最终j==(int)Math.Sqrt(num)+2
//
//当num是小于9的非2素数时（3,5,7），循环不进行，j的终值也就是初值3。
//若num=3，(int)Math.Sqrt(num)=1，j==(int)Math.Sqrt(num)+2
//若num=5或者7，(int)Math.Sqrt(num)=2，j==(int)Math.Sqrt(num)+1
//
//所以得出，这种判断对于一切非2素数均有效（其实2也是有效的，只不过最开始判断了）。
if (j == ((int)Math.Sqrt(num)) + 1 || j == ((int)Math.Sqrt(num)) + 2)
Console.WriteLine("{0}是素数", num);
else
Console.WriteLine("{0}不是素数,可以被{1}整除", num, j); //人性化一点给出不是素数的证据
}
Console.WriteLine("输入y退出，其他继续");
flag = Console.ReadLine();
} while (flag != "y" );
Console.ReadKey();
}
}
}

复制代码

这里说下程序中一大段注释下面那个判断，
if (j == ((int)Math.Sqrt(num)) + 1 || j == ((int)Math.Sqrt(num)) + 2)
这是一种比较精确的写法，但是也有可以笼统写，效果看起来会比较简洁
if (j > ((int)Math.Sqrt(num)))
因为如果num是合数（大于等于9的），循环肯定通过break跳出，j的取值情况必然满足循环判断条件：if (j <= ((int)Math.Sqrt(num)))。除此之外，我们可以不必细致去分析当num是质数的时候，两种情况j的取值究竟都是多少。

作者: 大虾挂了 时间: 2013-9-13 15:35
按照判断条件改为开平方之后的方法，同步更新下，输出不大于某个数（这个数大于等于2）的所有质数和：
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace 输出不大于某个整数的所有素数
{
class Program
{
      static void Main(string[] args)
      {
         int j = 3, i = 0;
         Console.WriteLine("请输入一个大于2的正整数,我们将给出不大于这个数的所有素数");
         int num = Convert.ToInt32(Console.ReadLine());
         List<int> sushu = new List<int>();//创建一个存储素数的集合
         sushu.Add(2);

            for (; j <= num; j += 2)
            {

                  for (i = 0; sushu[i] <= (int)Math.Sqrt(j); i++)
                  {
                     if (j % sushu[i] == 0)
                        break;
                  }
                  //里层for循环一次都不进行时（也就是j=3时）：自然满足判断条件
                  //里层for循环有进行的时候，如果通过break结束（也就是遇到因子了），必然有sushu[i] <= (int)Math.Sqrt(j)
                  //最坏的情况是sushu[i] == (int)Math.Sqrt(j)，也就是最后一次检验遇到了因子
                  //而如果一直未遇到因子，则跳出循环后必然有sushu[i] > (int)Math.Sqrt(j)
                  if (sushu[i] > (int)Math.Sqrt(j))
                     sushu.Add(j);
            }

         foreach (int k in sushu)
         {
            Console.Write("{0}\t", k);
         }

         Console.ReadKey();

      }
}
}

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2