题目:
求小于等于给定数值的质数之和。
质数是一个大于1的整数,
只有 1 和它本身两个约数的数叫质数。例如,2 是质数,因为它只能被 1 和 2 整除。1 不是质数,因为它只能被自身整除。
给定的数不一定是质数。
要求:
sumPrimes(10) 应该返回一个数字。
sumPrimes(10) 应该返回 17。
sumPrimes(977) 应该返回 73156。
代码:
<script type="text/javascript">
function sumPrimes(num) {
var p = [];
for (var i = 2; i <= num; i++) {
var flag = true;
for (var j = 2; j < i; j++) {
if (i % j === 0) {
flag = false;
break;
} //只有有其他约数就可以跳出循环了
}
if (flag) {
p.push(i);
}
}
return p.reduce(function(sum, cur) {
return sum + cur;
});
}
sumPrimes(977);
</script>
不过求质数之和其实有方法上的简化,一个数若可以进行因数分解,那么分解时得到的两个数一定是一个小于等于sqrt(n),一个大于等于sqrt(n),据此,上述代码中并不需要遍历到n-1,遍历到sqrt(n)即可,因为若sqrt(n)左侧找不到约数,那么右侧也一定找不到约数
作者:zooeydotmango
链接:https://www.jianshu.com/p/66220cb7977d
最新评论