00:02
这节课讲四除法,四除法是用来判断一个数是否是凑数的。根据定义。除了1和他自身外,不能被其他数整除的数叫做数数。根据定义,我们可以写一段代码。这个代码。除了1和本身之外。那么我们就从2到N-1之间变里,如果N能被其中一个数整除,那这个数肯定就是合数,否则就是质数。这是根据定义来的,所以这个算法肯定是不会有问题的。我们便利1~100之间有多少,有哪些,数数我们看一下运行结果。嗯,我们可以看到二三五,七十一,十三等等,这些数都是数数。嗯,根据定义来的算法,这个时间复杂度是N。
01:02
嗯,很明显这个算法速度太慢了,因此我们需要做,需要做优化,优化从两方面入手,第一个是缩小数范围。第二是减少次数。次数。首先我们看缩小示数范围。范,范围是从2到N-1之间便利缩小到2到根号N之内。为什么能缩小到根号N之类嘞?我们。假设如果N是一个好数,N肯定能等于A×B。嗯。A是比较小的数,B是比较大的数,4除法是从小到大便利的,因此首先会变列到A,这个时候N肯定能被A整除的,因此N已经被判断出是合数了,不会向下继续变利了,也就是说B不会被变利的。
02:09
嗯,这个时候,嗯,这个时候。就停止循环了。N临界点就是A和B相等,这个时候A就是√2。因此范围缩小到2到√2之内。这我们也看一下代码。我们看一下缩小示数范围代码是怎么写的。A小于等于的不管。首先是求根号N,也就是SQ。从2到根号N之类编。如果能被其中的一个数整除,那这个数就是合数。不能被所谓的数整除,那这个数就是支出。
03:00
我们也可以看一下运行结果。我们看一下坐角示数范围。我们可以看到,所有示数范围的结果和根据数数定义的结果是完全一样的。嗯,塑胶示数范围这个已经讲解完毕,然后另一个优化点是减少次数,次数。嗯。怎怎么为怎么可以减少次数次数啊,我们看一下这个终极优化。嗯,叔叔是叔叔。之之前讲的。这个I是从2到SQ,电力I加加,也就I=23456,这里面其中有何处?
04:00
所以N=C和DC×DC=A×B。也就是说,N和C都是合数。示数法是从小到大便利的,首先会便利到A。这个时候N肯定能被A整除的。所以N就是已经是合数,不会便利到B,不会不会便利到C了。一直这个减少次数,次数也是一个优化点,但是除数是数数。这个目前并没有找到叔叔的数列,因此我们只能退休。其次。嗯,退休,其次我们假设那个除数是基数,这已经说。减少次数,次数已经减少了一半。
05:00
嗯,我们直接看代码。处处是激素的情况。N=2,那那肯定是。叔叔。N倍2整除,那肯定就是合数,因此。首先求√2,因此可以从3直接变变到√2。注意之前都是I加加,这个时候I已经变成加等于2,这意思就就是说。这种便利的次数已经缩小到一半了。当然你里面的逻辑都都是一样的。我们也可以看一下预警结果。我们可以看到除数是基数,跟之前运行的结果都是一样的。
06:07
嗯,出租司机处。这个这是减少的次数,次数我们还可以继续优化一下。也就是除数是6N-1和6N+1的数。嗯,这个时候他已经排除了2的倍数和3的倍数,之前讲了除数是奇数,这是排除2的倍数。而除数是6 N-1和N+1的数就排除了。2和3的倍数。我们也直接看一下代码。
07:05
N首先N≤1的,那那肯定不是数数,N=2肯定是合数,肯定是数数,那你3也是数数。然后能被2整除,能被3整除了,那么这是。合数。这个时候已经排除了2和3的倍数。嗯,因此我们下一步就开始判断。首先求√2。SQ就是个√2。嗯。I=1这个T,我们就注意这个TT=6×A-1。
08:03
也就是6-1。然后判断这个这个数能被T整除,那这个数肯定就是合数。否则继续叛乱。然后下一步就判断6I+1,也就是嗯,这里面的6+1的数。然后判断一下。如果能被T整除,那那肯定就是合数,不能被T整除就是支出。如果我。如果这这一轮。判断不出来,那么进行下一轮也是A加加。这个时候。A就等于2啊。I=1的时候,那T就等于5和7 I=2。
09:02
66×2=12,也就是T=11和43。这上面这个T是11,下面这个T是13。如果体。已经大于了√2。那就直接退出循环了,这这个数已经被判断出是数数了。我们直接看一下运行结果。我们可以看到。结果跟之前的结果都是一样的。嗯,四处把讲解完毕。
我来说两句