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

接着优化还能优化啊，刚才呢，有同学又提到一个点，说关于这个位置的优化，哎，这个位置为什么还可以去优化呢？咱们刚才的优化呢，其实只是针对于这个非质的啊，那这块优化其实就涉及到关于质的优化了，嗯，这个I呢，其实可以不让它是I，比这个I呢，可以要小一点，可以是多少呢？啊，有同学说是二分之I是吧，还有别的情况吗？还有根号I，还有说根号I的，根号I那里先看怎么写根号A是吧，这个准确的应该是什么呀？就是更精确的，哎，更精确的其实是根号，只不过这个根号呢，咱们是这样写的啊，哎，这个咱们调的是咱们这个math类中的一个方法。哎，找到我们这个math是数学类，咱们昨天不也用过它这个rey吗？现在咱们用的是另一个啊，叫做script找S。

这哎，它是表示一个开方的意思啊。行，那这呢是做一个开方，但是这时候你要小心点，开方以后呢，这个位置要把这个数算进去啊，所以等号呢要加上，这个等号要加上，那好了，那我们首先呢，先说明一下这个问题，为什么这个位置不用到A减一了啊，咱本身呢，终止的是A减一，为什么到根号I就可以了呢。这个事呢，还是需要大家来理解一下的，哎，我们这以一个数轴为例，哎，这就别零了啊，一二吧，咱不是从二开始算的嘛，然后一直在这块去找，嗯，我先说一个数吧，这个数比如说拿100来说啊，可能稍微好说一点，这个原来的话呢，咱们是从这个二开始，别拿100了，因为100咱们在这break了是吧。换一个数97吧，好，这个数从二开始，咱们现在呢，想判断这个97呢，它是否是一个质数，我们呢要按照原来的方式是从二开始一直判断到96啊，97呢，确实也挺给力的，他真的还是一个指数，从二开始一路给你算到96，发现呢，你还真不是个指数啊，就是挺漫长的啊，算了这么多数，现在来说就是根本就不用到96。

啊，刚才有同学说我到二分之A，那你算下97除以二大概是多少啊，48点，48.5呢，我们一般除以二这个点五就不要了，是不是就48呀，好，那就相当于呢，我们刚才的优化策略呢，是想有一种优化策略是从二到48就可以了，48以后的就不用判断了，那我现在这个呢，说的更夸张点，我到根号97这个大概是多少？嗯，那九的话呢，是九九八十一，十的话呢，就100了，九点多是吧，九点多那就是九呗。啊，那就到九，那也就是说呢，更夸张啊，我根本连18都不用，我到九这块就可以了，就是二到九这块呢，你要判断一下，只要是没有是它的这个，呃，约束的是吧，我们就认为它就是一个指数了，你看这个多给力。

那下面我们来证明一下，为什么当根号就OK。对，你看这个情况啊，97咱们除以二的话呢，咱们刚才算了，实际上是得48.5是吧，04:18点五就是至少呢，就是你知道这个事，这一个数它除以啊，或者一个数等于吧，嗯，这个我没法擦了啊，先换个位置，这一个数等于这个数乘以这个数，如果我们前面这个数除以它的话呢，那就等于它要除以后边这个呢，就等于前面这个。哎，它俩其实是一对啊，对于我们九十七九，呃，97来讲，我除以二的话，其实这右边呢，这不就是有一个数给大家配对吗？你要是这个我们拿三去除的话呢，配对这个数一定比你这个刚才二配对这个数是不是要靠左了，因为要变小了，你这个数变大了，这个不就得变小了啊，那就这样一对一对的，一对一对的，这个能理解吧，哎，能理解啊，好，那你想我们这个数如果你除前面这个数出进了。

那你除这个数是不是也一定能出进啊，对，你除它除进来，那你除这个数不就自然然也就得到二了吗？所以其实我们没有必要呢，比较这一对数的这两头，你只要呢，比是不是这一一端就可以了，是吧？哎，我除以这个数呢，等于这个数你就没有必要再去除这个数了，我们就只除它就行了，哎，这个数你要是能除进了，那必然除它也能除进，这个除不进，除那边那个数也除不进，所以这样就一对一对一对一对，哎，随着你左边这个数越大，它最后除出来这个数也越来越小，它的一个临界点是是多少。对，临界点就是你除以这个数是不是还等于这个数本身呢？哎，这就是我们这个临界点，那这个除以这个数又等于这个数本身，那这个数呢，就是平方就等于它，那这不就等于开方塔，哎，所以我们这个极限值呢，就到这个开方这就行，只需要大家来考虑这个范围之内，你看有没有能够被它出尽呢，如果这块要是没有，你除这边呢，他也不可能有。

你想想你要除这边要是有的话啊，那不意味着你除完以后，这边这个数当时除的时候也能除进来。哎，就是这样一个逻辑，下面呢，再想一想啊，所以这块呢，我们把它改成小于等于这个X开方的啊。啊，稍等一等，这个咱们再说啊，哎这块呢，我就写完了，这个呢是咱们这个优化二，哎这个优化二呢，我们就是把它改成了这个开方，那这个时候大家想一想，我们这种优化是针对于哪些数是有效的。啊，正整数咱们本身考虑的不就是自然数嘛，说的没毛病是吧，这个这两个数有效啊，精确点来说，本身是质数有效吧，有效是吧，本身要是非质数呢，其实大家会觉得也有效，比如这100，我们就不用到99了，哎，你只需要算到这个十根号十就可以了，是吧，但事实上呢，其实你用不到到这块儿直接在这里边是不是就给你干掉了，哎，所以这块呢，其实都有效，但是真正执行力来说的话呢，对我们这个本身就是质数这一块呢，是一下子给它缩减了。

啊，就是对本身是呃质数的这个自然数，哎，自然数啊，这个是有效的，或者说呃，起到作用了啊，其实非指数呢也有效，只不过呢，你你还没钱，没等到你到这的时候，我在这块已经把你给过滤掉了啊不考虑了，行，那这样呢，写完以后，我们现在再来看一下这个时间到底花了多少啊。哎，编译一下运行。哎，1014这个好像感觉差点意思是吧，哎，优化二这个我们是改成这个开方的这个方式了啊1014，哎感觉他这个基础上好像变化不大，是这意思吧，这块的话呢，其实我们要再说一点啊，就是咱们现在是算到10万以内，就是当我们这个算法特别快的时候，其实这个输出呢，它影响了我们的一个执行，就是你每次输出这其实他要写出来这个其实它也会花时间，这个时间其实拖慢了我们的整个这个演示的这个算法时间。

那这时候我们就想把这个输出给他干掉，那输出干掉，你说那你到底这个算法对不对，他担心呢，是吧，咱们这样子整一下哈，我呢在这定一个变量，呃，因得型的一个count啊，先是一个零，用它呢来记录我们10万以内这个数的个数啊，哎，记住这个质数的个数，哎，然后呢，只要你是一个质数，咱们就别输出了。

因为这个输出呢，拖慢了咱们这个，呃，这个一个演示的，就像说这个CPU，你CPU你特别的这个跟另外一个CPU比你重性特别高，但是你写文件或读文件还得从硬盘中再加到内存这块，限制你这块CPU的这个展示的哈，所以我们只要你是一个指数，我这块就简单的做一个加加的操作，最后呢，我们这个在这输出一下啊，说有多少个质数。哎，个数为哎，加上一下，哎，我们这个叫抗，哎，我们简单的就光看一下个数来证明一下这个问题啊，把这个数字去掉，另外这样的话呢，我们还得回归到这个最初的这个来演示了啊嗯，那也就是说我们先啊我这样啊。来CTRLC一下。把它呢，先注释一下，我这块拿到以后，先还改成原来的，把这个等号去掉，改成一个I，这是咱们最初的这个方式啊，然后把这个呢，我们也注释掉，这是咱们这个都没有优化的时候，都没有优化，我们看这个个数，这个呢看看这个时间啊，咱们重新来计算一下，保存B。

运行啊，这时候你就等着就行了。对，这个喝口水绝对没问题啊。好出来了，9592，哎，9592个质数，然后时间呢是17110，这个我们直接就在这改了17110 OK，那接下来我们把这个优化一打开，边异运行，这时候河水可能有点悬啊。哎，1546那个数呢，是一样的，95921546。

15461秒多啊，跟这个跟刚才那个没差太多，然后下边呢，我们把这个注掉，把这个打开。这个CTRLX，这个我放到前面了，CTRLV一下。哎，后边这个我就不要了啊，这个咱们原来的这个这个策略啊，我保留一下吧，写到这儿啊这样。对，这个呢，我们换成是一个开方，注意等号加上下边break的打开CTRLS以下大家猜一下大概能有多少100多啊，九五九二十三毫秒。13啊，这是一个什么概念，看一下哎，原来呢是这么多，你除一下看看这是多少倍啊，个数一样的情况下呢，我们这个速度提升呢，是很大的一个翻多少倍的一个提升啊，所以我们得到一个结论什么呢？就是大家呢写程序，虽然说咱们这个CPU现在主频已经很高了，但是我们仍然要追求这个算法的一个优劣，还是要比较算法的，所以呢，呃，像数据结构加算法这本书啊，讲算法的还是非常有意义的啊呃，不同的算法你会发现实现的这个效率呢，是可以查出很多来的，比如说你去这个中国移动或者联通，你去搜一个你的这个前几个月的这个账单啊，这个呢一点两秒钟就出来了，你那点了以后呢，咱这得抽根烟的时间才能查出来啊，那这个体验就差很多了啊，包括呢，你看大家呢，现在去百度上去搜任何一个信息，比如说你搜个美女是吧，啊，一搜立马就出来了，紧跟你现在这个诉求是吧，比如说你搜了个美女五分钟以后才出来，这个感觉早没了啊，这体验就差很多。

啊，诶，那你想想这个百度呢，这么大的庞大的数据量的情况下，怎么能够保证这个查询速度极快，哎，这里边呢，就有很多的算法在里边了啊诶需要大家呢，慢慢的不断的去探索去学习的行，那通过这个问题呢，咱们来说明一下，一方面啊，会做这道题，这是一道笔试题，另外呢，哎，就是你要能够写出这样的一个策略的这个支出输出啊刚才那个策略呢，哎，这个只能算是一个合格是吧，然后这个呢，那就算是一个优秀了。