首页 > 代码库 > Sum All Primes

Sum All Primes

题目

求小于等于给定数值的质数之和。

只有 1 和它本身两个约数的数叫质数。例如,2 是质数,因为它只能被 1 和 2 整除。1 不是质数,因为它只能被自身整除。

给定的数不一定是质数。

测试用例:

sumPrimes(10) 应该返回一个数字。
sumPrimes(10) 应该返回 17。
sumPrimes(977) 应该返回 73156。
思路
质数,也叫素数。定义:约数只有1和他本身的数。举个栗子:2,3,5,7...
一般的判断条件写作循环2到他本身,而求小于等于给定数值的质数之和只需要从2循环到他本身即可
 1 function sumPrimes(num) { 2     var sum=0; 3     for (var i = 2; i <= num; i++) { 4         var isPN=true; 5         for(var j=2;j<i;j++){ 6             if(i%j==0){ 7                 isPN=false; 8                 break; 9             }10         }11         if(isPN) sum+=i;12     }13 }

但这对于大数值的计算过程将是漫长的,所以我们可以对以上算法作出一定的优化。到这里我猜有人就会问了,作为一个前端为什么还要懂算法或者说要学会对算法进行优化?如果你已经对本文持怀疑态度那你可以点击右上角红叉了,谢谢

 

 

看来你已经决定留下来了。那我们应该怎样对以上算法进行优化操作?先卖个关子。

约数总是成对的存在。以下格式为[A,B] 数值本身简写为N

举个栗子:6,我挺喜欢的一个数字,毕竟我6666。嗯...说正事,6的约数对有两种情况[1,6] [2,3]。

再举个栗子16,约数对可以解析为[1,16] [2,8] [4,4]

为什么没有[8,2]甚至[16,1]呢,因为从对数上来说[2,8]和[8,2]是相等的。那么意味着什么?意味我是吴彦祖吗?对的我就是。除了这个结论同时还意味着我们在判断2是否可以被16整除后可以跳过8是否被16整除。但是应该从2循环到哪里呢?

我们再来看几个栗子,9可以解析为[1,9] [3,3]  25解析为[1,25] [5,5].........发现了吗?

我们应该避免的是约数中A比B大,因为如果A比B大了在A可以被整除后说明这个约数对我们是必定计算过的,这只是重复造轮子增加内存的消耗而已。

不信你看24 约数对可以分为[1,24] [2,12] [3,8] [4,6] 这就是24的全部约数对了。怎么验证?可以让A继续增长,[6,4] [12,2] [24,1] 这些是我们上面全部计算过的内容了,只是换了一下顺序。

所以我们可以循环2-A的最大值就行了,A的最大值就是在AB一样大的时候,见 25 16 9。那么A什么时候与B一样大?没错就是√N

所以可以得出一个结论,在N只需要判断2到√N是否能整除就行了。只需要把第二个循环的i转变成√i即可。√在代码中为Math.sqrt(X),也可以用A*A<=N代替

有同学就问了,为什么要这么麻烦?在碰到能够整除的数值直接跳出不就行了吗?

再举个栗子:49999一个质数,在按原本的算法循环应该是判断2-49998是否能被49999整除。而使用了√后,只需要判断2-223(√49999<224)是否能被49999整除即可。数值越大优化越明显

本期关于质数的一点小优化到此为止,过几天会有进阶版的优化,有兴趣的可以移步一观:)

 

Sum All Primes