day05_Java基本语法与项目一/12-尚硅谷-Java语言基础-质数输出的算法优化一

好，下面咱们在这个题目的基础上呢，对它进行优化，就是说如果大家去这个笔试的时候，出了这个问题，说100以内指数的输出，你写成这样的只能算是马马虎虎还可以啊，跟这个写不出来的比呢，那肯定还是不错的啊，但是呢，这个写的效率呢比较差。那下边呢，我们对这个代码呢，进行一个优化，通过这个呢，咱们也来也来说明一下，就是不是说这个CPU主频特别高了，然后呢，算法你就可以乱来啊，你会发现呢，不同的实现方式呢，这个效率能查出来很多啊嗯，那我把这个代码整个呢，先都复制一下，说C再新放到一个文件里面啊，CR一下粘过来，还有一个问题，此时呢，我们是对前面这个的一个优化啊，CC啊这个对，我们这个在点Java文件中。这个问题的优化啊，CC1下行，那下边呢，我们来看一下有哪些可以优化的这个空间啊，大家看一看，我们这呢，是100以内的一个指数输出，嗯，哪些位置我们可以考虑去优化一下，让这个效率更高呢。

有没有同学能想到的，怎么着往除那些质数是吧？七啊，你把那些抽出来都抽不能除是啥意思，能。嗯，懵啥意思，你说让那个街是不能等于235，就你那个没明白啊，刚才有同学说，他说我这时候我判断这个，你这个先等一等啊，应该组织一下语言，哎，刚才有同学说说我这个判断的时候呢，我把这个偶数都抽出来，偶数肯定都不是这个质数了，是吧，然后我呢，只拿奇数里边去判断这个可以吧，可以对于这个题目来讲的话呢，其实是能够少，就是瞬间的以下这个数出就减半了啊，能减半，但其实从这个算法层面，咱们算法是这样子啊，大家可能没有，呃接触过这个数据结构，数据结构里边它有这样一个意识啊，就是它会算这个叫时间复杂度，实杂度，就是咱们这个问题呢，这个NN就代表呢，就是从二到100，我们假如就其实N不完全是100，因为咱们从二少了个一是吧，哎，你可以按成是N减一呗，哎，像这种N减一，如果我们从时间复杂度的角度来。

讲它也是on级别的，我们只是看他这个次幂的方式啊，次幂这个N减一呢，它从这个时间拉来讲是on级别的，On的还是O，哪怕说你是一个2N，这个时候呢，我们这个它的复杂度呢还是on，你要是二分之N，这不就大家想说的情况，就本身呢，我们这有100个数，然后呢，我们复杂度呢是然后呢你对你二分之N的话呢，从复杂度上来讲，其实还是就是它还属于一个量级上的。

时间呢确实会少，但是呢，他谈不上说，比如说你那个发了是十秒，我这个发的是一秒，你是两位数或者是一位数是吧，这种叫量级上的，可能你那个呢是花了十秒，这个花了12秒，咱们认为它在同一个量级上，哎是这个意思啊，哎，但是刚才大家提的这个说我只考虑这个这个基数啊，这确实是能减时间，但是减的有限，那我们现在再来考虑，就是减的可以更夸张的。嗯，啊对，刚才有个同学说提到一个开发的问题哈，还有别的吗。啊，还有个提到条个break是吧，考研的数据结构啊，数据结构它是一个通俗的一个知识啊，就是它区别具体的言，比如我们数据结构的话，其实通常数据结构大家都是用C语实现的，对吧？然后呢，我们Java的也有Java版的这个数据结构，然后你也有这个，比如Python版的数据结构，还有其他语言版本数据结构啊，包括skyla版本啊，公语言版本啊，数据结构它是研究这个数据在底层我们应该怎么去存，那咱们Java的话呢，回头会讲集合，那就会讲哎，Java是怎么来实现这个数据的批量存储的，那就用Java实现，就是Java版本的数据据。

啊，那你要去别的语言，那用别的语言版本的数据结构，所以大家如果去京东上买书，你输入数据结构，它下面会一般写着说Java语言描述版是吧，Python语言描述版，C语言描述版都会写，如果都没写，那通常默认呢，就是C语言版，哎，它是这样的啊，就是它是一个，它是一个讲数据怎么存储的一个一个技术，然后呢，我们是通过不同的语言去实现这个技术而已，啊是这样子的啊行，那就如说大家呢，如果你要想看数据结构关心的话呢，那咱们现在学Java，你回头呢就先看Java版的，当然C语原版，你你学了Java语法以后，因为Java不是类似的嘛，你也能看得懂。

啊，但是毕竟你是做Java的，所以你主要关注它就可以啊行诶刚才呢，其实有同学提到了两个策略啊，哎，刚才说到了一个呢，是说这块的一个处理，另外呢，是在这里边加上一个break，那咱们一个一个来，那这两个也确实是咱们现在要讲的优化，那首先呢，先说这块啊嗯，我们在这个if当中，这个if flag呢改成false以后，我这紧接着加个break，我说呀，加上break以后这个效率呢就能提高很多，那先在体会一下为什么加上break克就可以变快。对，就是说一旦呢，你这个I要是发现有一个阶呢，被除尽了，后边的阶呢，就别算了，比如说100，咱们原来呢，是不是从二一直到99都得出一次。

哎，其实呢，你就100除二的时候，是不是就已经除进了，既然已经除进了，就别再除三，一直到99了，没啥意思，也没有意义，因为你已经不是一个指数了，还除什么呢，是吧？所以这个时候呢，我们加上一个break，哎，这呢就是咱们所说的这角优化。这个一啊，这样的一个方式啊，那么加上这个break呢。其实大家再想一下，我们刚才举例的，举的这个数呢，是100啊，这100本它不是个质数啊，另外本身这个数是一个质数的话，这个有作用吗？本身是一个指数90A97是吧。97式是吧，比如说97，我这加对97有效果吗？没有。

咱们因为你这个从二期一直到96都没出进过，其实对他没效果是吧？呃，因为我们这个优化一呢，它呢，呃只对哎本身呢，非质数的这个哎数是有效的啊，本身哎非质数的这个自然数但是有效的，哎这个呢，就是我们扣的又更细了啊，那加了它以后呢，我们说这个效率又提高了，那你怎么证明它提高了还是没提高，不能你嘴上说了就完了，是吧，我们得证明一下啊，那证明的话呢，咱们就得这样啊，我呢，呃在我们这个程序，呃，这个flag定义完以后，我在这吧，在这呢我们看一下呃加跟不加花了多少时间，哎我们就知道到底是差多少了啊这个时间呢，咱们之前没有出现过，在这呢，我们引进来一下。在咱们API里边，API我这可以有工具栏，有一个新建工具栏，我有一个文件夹呢，就叫API哈，选择一下就在这能看到了啊，诶在这呢，我们去找一个类叫做system，其实也用过啊，System下面它有个方法讲这个啊，Current ten minutes，它返回的就是当前的一个时间，它是以这个毫秒数的方式呈现的啊呃，返回的是一个浪形的值，诶按说时间应该是一个年延日十分秒啊，但是它反回是个浪形，为什么是浪形呢？那这样它反过来是这样的一个一个一个距离是用毫秒数来衡量，的确当前的咱们这个时间和。

1970年1月1日午夜00:00:00到现在的一个。毫秒数，嗯，这呢是一种时间的计算的一种单位啊，一种标准啊，这个咱们就不关注了，嗯，那也就是说呢，我们这个浪形的值呢，就是从1970年的那个1月1号00:00每秒到咱们现在这个时间的一个毫秒数，用浪形的一个值保存的行，那咱们就可以这样，首先咱们先see这点，哎，Current time，哎，Me，这个你要不会写，你就直接从这块给它CTRLC一下是吧，过来了啊哎，这样的话呢，我们得到一个浪形的我叫做一个start开始的一个毫秒数，哎，这个获取当前时间的这个毫秒数，哎，准确的说应该当前时间距。

距离哎1970年，嗯，1月1日，嗯，然后00:00，哎，零秒是吧，哎到现在的一个毫秒数，单线线距离这的毫秒数行这样就行，这样呢，我们计算一个毫秒数了，然后当我们把整个这个程序执行完以后，咱们在这个位置，我再算一下当前的时间。CTRLC这个位置，这个我们再换一个变量，我叫做N，然后这两个的时间差就是我们这个程序执行所花费的毫秒数。

哎，所花费的这个时间为这个毫秒跟秒之间的关系是什么？什么换算千啊，千为单位就是一秒呢，等于1000毫秒，那这个注意啊，行，那这样的话呢，我们就就能计算这个时间了，那计算这个时间呢，咱们先把这个break呢给它去掉，对吧？先去掉啊先去掉呢，我们看花了多少时间，但这时候呢，我们这个样本呢，又有点太小了，不足以呢，让我们感受到这个区别，我们给他来的大一点，10万再夸张一点啊，计算10万以内所有的质数。啊，这个改成10万啊，啊，这个我们也给他改一下吧，改成10万了是吧，少一点这少一点。

来，这时候我们先跑一下，看看这个没有优化之前花了多少时间。Java c frame number test一点Java猜测一啊，这行。哎，这是两万多是吧，越往后就越慢啊，因为你要判断的数呢，就那从二开始到小于它本身这个就越多了，哎，大家呢，其实有一喝口水的时间啊。好，这个时间呢，计算出来20多秒。2010520105，我在这记录一下啊。零，这是我们没有化的一个时间，现在呢，这个开以后我们现在来。

编译运行。OK，看一下两秒钟啊，2585。哎，这个是咱们这个优化一加上这个break的这个情况啊，2515585这个呢，这不是很显然这个时间就查出来了，这个水呢，可能没有这个时间了啊好，这个呢是。