00:00
这节课讲欧拉塞,欧拉塞的功能跟上节课讲的S赛的功能是一样的,都是批量找输入,比如11~100之间的左右输出。从时间复杂度来说,欧拉塞到时间复杂度是。而之前讲的S塞的时间复杂度是N乘以那个勒个N,所以欧拉塞比塞的快。当我的实际运行结果是,埃塞总是比欧拉赛的快。这是为什么?这是因为欧拉塞的常数项嗯,大于S塞的常数项。嗯,欧拉赛的算法步骤是怎么样的?这个我就不念这段文字了,这太文绉绉了。我直接看,直接看1~100这个例子。这个1是特例,所以变红1是1,不是数数。
01:06
然后便利到2字这个位置。2。它并不是红色,所以它是数数,所以我把2给记录下来。2记录下来过后,然后变成2的倍数,这个2只能乘以乘以上面的2,所以。等于4,所以把4标红。因为他这只有一个数数,所以这个8就不需要标红了。然后进行下一次便利。下一次便利就是三三。山并不是红色的,所以山也是树,树。把3给记录下来。然后做注意。
02:00
这个3。是乘以数数数表里面的2。N3×2就等于6,所以标红。然后。然后再判断3。能否被2整除?实际上是不能整除的。所以。所以3×3。3×3=9,所以把9给标红。然后3÷3这个呢,肯定能整除了,所以直接就不需要下次变列了,也就是说12这个不不需要标红了。然后便利是。4它是合数,所以是不会记到数数表里面。
03:01
但是他会记一下它的倍数,先记倍数。4×2。就等于8了。所以把。爸爸给标红。然后标红过后,然后4÷2肯定能整除的,所以这个16就不需要标红了。然后进行下一个5。五五不是红色,所以它5是数数,把5给记录下来。然后5乘以输数表里面。第一个数,5×2。就等于10了。所以把屎给标红。让5乘以数数表里面第二个数3。5×3=15,所以把15给标红。
04:06
嗯。五五不,不能被三整除,所以进行下一个就是5×5,注,注意不,不是5×4哈。因为输入表里面235。这个不不能5乘一次把把20给标红了,这个21是不不能标红的。5×5,也就是25,把25给标红。嗯,25。5×5已经5÷5能整除的,所以这个30啊,35啊,这就不需要标红了,然后进行进行下一个数的变利6。首先判断6是否是质数。因为它是红色的,所以肯定不不是数数。然后就乘以数数表里面的第一个数。
05:01
6×2。而它是等于12的,所以把12给标红。标红过后再判断一下6是否能被2整除,很明显能证除的能证出呢,直接不掉,所以就不需要下一次便利了。根本就没有6×3的这个操作。进行6变的完过后,然后就是7了。77并不是红色的,所以7它是数数,先把数数给记录到数数表里面。嗯。然后7×2。7×2=14。啊,十字给标红。然后7能否整除2明显不能了,所以7×3。七七乘以3=21,把21给标红。
06:07
嗯,7×7不能和不能整除三。所以7×5注,注意这个地方不,不是乘以4 4×5。七七乘以5=35,把35给标红。嗯,37 7÷5都不能整除,所以进行下一个便利就是7×7。七七四十九,然后把49给标红。7和7肯定能整出的,所以就break掉,就不不需要后面的背出了。然后我们再看把。之前讲了,S3只需要擦掉2357的倍数。
07:01
就是所谓的合数都跟都标标记出来了,但是欧拉塞不一样。因为后面的好多好多火树并并没有给标记出来。所以从8开始,我们还是还需要标记的。8首先判断8是否是。字数。明显不是字数,所以不不会记录到输出表里面。然后8×2。88×2=16,把16给标红。8能能整除2,所以break掉就8×3 8×8×7就不不需要标记了。然后进行下一个9。酒。首先判断9是不是数数,很明显9不是的,所以不,不需要记录到数字表里面。
08:00
但还是需要标记倍数9×2。9×2=18,把18标记为红色。9÷2。不,不能整除,所以还还是需要9×3。9×3=27。把SG标红。就能就能够整出3,所以。所以所以不不不需要继续标记啊,直接break掉,然后进行下一个标记。下一个就是死了。首先判断10是否是数数,10肯定不是数数,所以不不需要放在输数表里面。然后进行下一个。求10的倍数,10×2=20。20、标记为红色。
09:00
然后10能被2整除,所以就break掉,就不需要进行标记了,再看下一个11。十一,11并没有标成标记成红色,所以11肯定是数数。然后标记完成过后,然后11×2=22。二十二、标记为红色。然后11他肯定不不能整除二的。所以进行下一步,11×3。11×3=33。把3标记为红色。嗯,11÷3肯定不能整除的。所以进行下一步的备注。11×5,注意注意这个地方是5了,不,并不是4。
10:01
因为输出表里面没有4的,所以10 11×5=55。啊,55标记为红色。嗯,11÷5并不能整除,所以进行下一步。11×7=77。不要就红色。嗯,11。除以7不能整除的,所以进行下一步的被除。11×11=121,一百一百二十一已经超过100了。所以就不用标记了。然后进行下一个数字的判断。12。10。首先判断12是不是叔叔,很明显不是。嗯,不是,然后进行下一步判断,就是12×2=24。
11:03
244标红色。然后12÷2能证出,所以直接就掉了,就不不需要12×3了。看下一个数字13。13。紫山不是红色,所以它是树,树把山给记录下来。然后13×2=26。26、标记王子。13除以二不不能整除,所以13乘以乘以3等于三三十九。然后13÷3不能整除,所以13×5=65。嗯。
12:00
13÷5不不能整除的,所以13×73×7=91。别王者。13÷7不不能整除,所以13×11 13×11已经超过100了,然后后面也就不管了。我们看下一个数字4。14。实施它是合数,所以不不需要记录到输数表里面。然后再再再求它的倍数,14×2=28。二十八、标记红色。14÷2能整除,所以不,不能乘以3了,也不能乘以5。就直接断掉进行,下一个数字是55,它是红色,所以不需要记录到数据表里面。然后15×2。
13:01
15×2=30,把30标记红字。事除以二,不,不能,不能整除。所以就看15×35×3=45。把字数标记为红色。嗯,15÷3能整除,所以就直接不掉,所以15乘以五,15×7这里就不用管了。看下一个数字16。十六十六它是红色,所以不需要记录到数据表里面。然后,然后16×2=32。把三色给标注红色。16NUMBER证出。所所以,所以就直接不乐意扣掉,不需要16×3了。看下一个数字17 17并没有标记成红色,所以17它是数数。
14:00
记录下来。看11×2。等于34啊,30给标记为红色。17÷2不不能整除,所以需要10,需要下一步17×3。17×3=51,把51可以标记黄色。嗯。17÷3不能整除,所以17再乘以5。17×5=85。标记为红色。嗯,17÷5不不能整除,所以进行下一步,17×7。17×7。17×7等于等于多少呢?算一下。
15:03
17×7等于。119已经超过100了,所以就不不用管了。看下一个数字18。18是红色,所以不需要记录数据表里面。然后18×2。18×2=36。把36标记为红色。棋盘能卖2整株,所以就不需要标记了。看石油,石油并不是红色。所以记录到数据表里面。然后19×2。等于38。把38给标记为红色。只有初一二不不能振作。所以19×39×3等于。57。
16:01
把51标记为红色。19÷3不不能整除,所以19×5。19×5等于。95。19÷5不不能整除,所以19乘以七,19×7已经超过100了,所以就不用管。看20。20。20它是合数,所以不需要记录到输入表里面。20×2=40。把40标红。嗯。二十,二十能被二整除,所以就不不用管了。看21。21它是红色,所以不需要接到数据表里面。
17:05
21×2=42,把42标记为红色。21÷2。不能整除的,所以21再乘以三二十一乘以3=63。把六三给标记红色。21÷3能证出,所以21不需要乘以5了。看下一个数字22。22这这个数字。它是合数,所以不需要记录到数据表里面。22×2=44,把44个标红。22除以二能整除,所以就不用管了。看下一个数字23 23没有标红,所以把23给记录下来。他是二三十叔叔。
18:02
然后23×2。23×2=46。46、标红。N3÷2不能整除。所以23×3。23×3等于多少?嗯。69。嗯,23×3等等于69。23除以上不不能整除,所以23乘以五,23×5已经超过100了,所以就不用管了,23×7这这里都不用管了。看下一个数字24。244。它是红色,所以不需要记录到数据表里面。X4×2=48。把标红。24÷2能挣着,所以就不需要。
19:03
不需要下一步了,看25。25。25是红色,所以不需要记录数据表里面25×2=50。标。25。25÷2不能整除,所以25×3=75。25÷3不能整除,所以25乘五二十五乘乘以5。已经超过100了,那那那就不用管了。看下一个数字26。26。26它是红色的,所以不需要记录数据表里面26 26×2=52。5色标红。
20:01
25÷2能整除,所以就不用管了,看下一个27。27。它是合数,所以不需要记录到数据表里面。21×2=54。嗯,21除以二不不能整除。四二十七乘以3。21×3=81。把81变红。嗯,27除除以3能整除,所以不,不需要27乘数了,看下一个数字28。28。它是红色,所以不需要记到数据表里面,28×2=56。嗯,标红。28÷2能证出,所以就28不需要乘以3了。
21:04
看下一个数字,二十九,二十九。29并没有标红,所以它是数数。嗯,29×2=58。29除以二不不能整除,所以29×3。29×3=87。29÷3不不能整除,所以看二十二十九乘以五,29×5已经超过100了,所以就不用管了,看下一个数字30。三三十它是红色,所以不需要记录到数据表里面。然后看30×2=60。
22:00
嗯。30÷2能整除,所以就不用管了,看31 31它是速度,所以记录下来。嗯,31×2=62。嗯,31除以二不不能整除,所以31×3=93。嗯,31÷3不能整除,所以31乘以五,31×5已经超过100了,所以就不用管了,看下一个数字32。嗯,32它是红色,所以不需要记录数据表里面。32×2=64标红。
23:00
32除以能整除,所以就不用管了,看下一个数字33。三三它是红色,不需要记到数据表里面。33×2=66,把66标红。嗯,13除以二不不能整除。所以33×3=99,把99标红。嗯,三三。除以3能乘除,所以就不需要下一次了。看下一个数字344。344它是红色,所以不需要记录数据表,34×2=68啊,68标红。34÷2能整除,所以就不用管,看35。35。它它不,它是合数,所以不需要记录数据表里面35×2=70。
24:05
嗯,三三十五除以2不不能整除,所以35×33,但是35×3已经超过100了,所以就不用管了,看下一个数字36。36它是合数,所以不需要接入到数据表里面。36×2=72。嗯,36÷2能整除,所以就不用问,看下一个数字37 37没有变红,说明它是数数。把37给记录下来。47×2。嗯,等于多少呢?74。啊,其实标红。嗯,37除以不不能整除。所以看37×3。
25:02
37×3>100了,所以就不用管了,看下一个数38。嗯,38。38它是合数,所以不需要记录数字表里面38×2=76。把76给高红。48÷2能证出看下一个数字。3。39不,不需要记录到数据表里面,因为39已经标记为红色了,39×2=78。把78变红。39除以二不不能整除,所以39乘以三三十九乘以3已经过100了,所以就不用管了,看下一个数是40。嗯,40它总子,所以不需要记录数据表里面40乘以下等于80。
26:03
嗯。40÷2不,不能整除,能整除,所以就直接break掉了,就不用管了。看属于。41它不是红色的,所以它是数数,把41给记录下来。十十一乘以2=82。41÷2不能整除,所以41乘以三四十一乘以3已经大于100了,再加一个数字42。四四十二它是红色,所以不需要记录到数据表里面,42×2=8是24。感觉红色。4除要能成熟,所以就直接不能扣掉了。看下一个数字四十三,四十三并没有标红。所以把43给记录下来,43它是叔叔。
27:03
43×43×2=86。嗯。四三除以2。嗯,不,不能整除,所以43乘以三,43×3>100就不用管了,看下一个数字。它是红色的,所以不需要放在数据表里面。40×2=88。嗯,40正除以2能证除,所以就直接掉再加一个数45。45。它是红色,所以不需要记录数据表里面45×2=90。把就是标。45÷2不能整除,所以45×3。45×3已经大过100就不用管了。46。
28:04
嗯,46它是红色,所以不需要放在四边里面,46×2。46乘以等于92,把92标红。46÷2能整除,所以就不用管了。47。17、他是他不送子,所以他是叔叔。把司机给记录下来。嗯,41×2=94。嗯,47÷2不能乘除,所以47×3已经大过100了,就不用管了,48。嗯,48。它是字,所以不需要记到数据表里面,48×2。等于96。
29:00
嗯,48÷2能证足。就不不用管下一步了,看下一个数字。四十九,四十九它是红色,所以。不需要接入到数据表里面,19乘以等于98。把98标记为横竖。49除以二,嗯,不能整除了,所以49乘以三四十九乘以3已经大过100,就不用管了。50。50 50它是红色的,所以不需要记到数据表里面,50×2=100。把100标红。嗯。嗯,50÷2,嗯,能证出,所以就直接掉。嗯,到了这个时候,这个叔叔已经全部。这个合数已经全部标记好了,剩下的都是数数,我们可以看到这个数数2~47。
30:03
已已经找出来了。呃,后面的后面的叔叔直接直接便利51~100就。直直直接直接找到叔叔就就可以了。们再回过来看一下。这标记的过程我们也已经看到了,这标记红色并没有重复的标记,而S它是有重复标记的。因此,欧拉塞的时间复杂度更低。优点就是比起S在的时间复杂度低一些,而缺点比起S在难以理解,虽然时间复杂度相对较低,但是运行时间总是要慢一些。跟埃斯塞的区别?有如下几点。
31:00
欧蓝山指标记。小于等于A平方的A的倍数,而SC标记的是大于等于A平方的A的倍数。第二点S3的A的变量范围是2到根号拉3的的变量范围是2到N÷2。第3点I标记的倍数。直到超出范围为止,而欧拉在标记哀到背处中途是有可能的。第4点。SI在标记合数的过程中不会用到输出表。而欧拉塞在bug合作的过程中未用了数据表。我们看一下代码。这个代码我直接看魔除的。嗯,魔球的这个。P.它它是标记输入的,也就是。
32:03
这样。Now就是play的个数。这个闹它是会动态增加的。因为刚开始的时候是没有输出的,所以就为0标标标记一次,这个捞会加1的。而visit就是标记表。当然这个地方。这个force就是,嗯,就是数数。哎,处就是合数。我们直接看一下。代码。首先这个输数表里面肯定是没有输出的,然后I从2开始变历。这个2。而且他。那他肯定是指数。
33:02
嗯,所以把把这个I放到输出表里面。然后这个个数肯定也是会加1的。然后接。从零开始。这是。也就是输入表里面的第一个元素。这个是输,输数表里面第一个元素,再乘以I是IG,就是2,然后这个倍数标记为好数。标签完成过后,然后就看一下模除就是。2除以第一个数。如果能整除就掉,如果如果不不能整除,那就。那就会继续下一次的循环。
34:01
注意这个地这个条件。J小于等于然是J小于然是什么意思呢?也就是小于这个数数表的个数。而后面这句代码就是。就是推接乘以I,如果如果的如果是大元脑,那那他也不会循环了,就只就直接退出循环。这欧拉塞讲解完毕。
我来说两句