果然有心事是睡不着的,最终版贴出- 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:今天累翻了,话说能不能再给点技术分,~~~~(>_<)~~~~ |