当前位置: 首页 > >

JS实现欧拉计划

发布时间:



JS实现 欧拉计划
第一题 3的倍数和5的倍数第二题 偶斐波那契数第三题 最大质因数第四题 最大回文乘积第五题 最小倍数第六题 *方的和与和的*方之差第七题 第10001个素数第八题 连续数字最大乘积第九题 特殊毕达哥拉斯三元组第十题 素数的和持续更新中...



第一题 3的倍数和5的倍数

如果我们列出10以内所有3或5的倍数,我们将得到3、5、6和9,这些数的和是23。求1000以内所有3或5的倍数的和。


/*js实现代码过程*/
var num = [];
var sum = 0;
for (var i = 0; i < 1000; i++) {
if (i % 3 === 0 || i % 5 === 0) {
num.push(i);
}
}
for (var j = 0; j < num.length; j++) {
sum += num[j];
}
console.log(num);
console.log(sum);

输出为



Array(467) [ 0, 3, 5, 6, 9, 10, 12, 15, 18, 20, … ]
233168




第二题 偶斐波那契数

斐波那契数列中的每一项都是前两项的和。
由1和2开始生成的斐波那契数列前10项为:1, 2, 3, 5, 8, 13, 21, 34, 55, 89…
考虑该斐波那契数列其值不超过四百万的项,求其中为偶数的项之和。


var sum = 0;
var arr = [1, 2];
var i = 0;
while (true) {
arr[i + 2] = arr[i] + arr[i + 1];
if (arr[i + 2] > 4000000) {
break;
}
i++;
}
var e_arr = [];
for (var j = 0; j < arr.length - 1; j++) {
if (arr[j] % 2 === 0) {
sum += arr[j];
e_arr.push(arr[j]);
}
}
console.log(arr);
console.log(e_arr);
console.log(sum);

输出为



Array(33) [ 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, … ]
Array(11) [ 2, 8, 34, 144, 610, 2584, 10946, 46368, 196418, 832040, … ]
4613732




第三题 最大质因数

13195的所有质因数为5、7、13和29。
600851475143最大的质因数是多少?
分析:
如果不优化代码,求解的时间会很长。
首先600851475143不是一个偶数,所以在取因数的时候完全可以从3开始,只取奇因数;
其次先算一算600851475143的最小最大因数。


var number = 600851475143;
for (var i = 3; i < number; i += 2) {
if (number % i === 0) {
console.log(i, number / i);
break;
}
}

输出为



71 , 8462696833
[Done] exited with code=0 in 0.179 seconds



这样就大大的减少计算量,再求解


//首先求出number的所有奇因数
var max = 8462696833;
var arr = [];
for (var i = 3; i < max; i += 2) {
if (max % i === 0) {
arr.push(i);
}
}
//再取出奇因数中所有的质数
var even = [];
for (var j = 0; j < arr.length; j++) {
var flag = true;
//用开*方根和break也能提高性能
for (var k = 2; k < Math.sqrt(arr[j]); k++) {
if (arr[j] % k === 0) {
flag = false;
break;
}
}
if (flag) {
even.push(arr[j]);
}
}
//取出even数组中最后一个元素
console.log(even[even.length - 1]);

输出为



6857
[Done] exited with code=0 in 39.833 seconds



最后还是花费了40秒,先这样吧。。



第四题 最大回文乘积

回文数就是从前往后和从后往前读都一样的数。由两个2位数相乘得到的最大回文乘积是 9009 = 91 × 99。
找出由两个3位数相乘得到的最大回文乘积。
分析:首先,9009的个位和千位一样,十位和百位一样。所以判断是不是回文数,就判断它每位是不是一致的。其次,999*999=998001,所以三位相乘最多获取六位数。下面就可以写代码了


var res = [];
for (var i = 100; i < 1000; i++) {
for (var j = 100; j < 1000; j++) {
var num = i * j;
var str = num.toString();
var arr = str.split("");
if (arr.length === 6) {
if (arr[0] === arr[5] && arr[1] === arr[4] && arr[2] === arr[3]) {
res.push(num);
}
}
}
}
//将数组降序排列,得到最大值
res.sort(function(a, b) {
return b - a;
});
console.log(res[0]);

输出为



906609
[Done] exited with code=0 in 0.471 seconds



PS: 刚看了 apply() 方法,真是方便啊,最后根本不需要使用 sort()方法。将最后的代码改成


//使用Math中的 max() 方法,得到最大值
//第一个参数是this指向;第二个参数是数组
var max = Math.max.apply(Math,res);
console.log(max);


第五题 最小倍数

2520是最小的能够被1到10整除的数。
最小的能够被1到20整除的正数是多少?
分析:
首先我们从2开始连乘到10,1x2x3都没问题;
等到x4的时候,可以发现在1x2x3中有一个2,4/2=2所以只需要 x2就够了不需要*4;现在的连乘数列是 1x2x3x2。
x5也没问题;于是数列变成了 1x2x3x2x5
x6的时候发现在数列中有一个 2x3=6,所以不需要6;
x7的时候,数列变成了 1x2x3x2x5x7
x8的时候,发现数列中有 2x2=4,还缺少一个2
x9时,数列中只有一个 3,还缺少一个3
x10时,数列中已经有 2x5了
所有我们可以得到 1x2x3x2x5x7x2x3 =2520
也可以看出这其实就是找1-10的因数的过程,如果有因数就相除得到商
分析完毕,下面是编程过程…


var arr = [2];
//从 2开始连乘到 20
for (var i = 3; i <= 20; i++) {
var index = 0;
var res = i;
for (var j = 0; j < arr.length; j++) {
//判断 i有没有的因数,如果有就除以得到商,一直有一直除,最后就是 1了
if (i % arr[j] == 0) {
index++;
res /= arr[j];
if (res <= 1) {
res = 1;
}
}
}
//如果 i没有因数,直接添加到数组中
if (index == 0) {
arr.push(i);
} else {
//如果 i有因数,就把最后的商添加到数组中
arr.push(res);
}
}
console.log(arr);
var num = 1;
//数组连乘就是最小的倍数
for (var k = 0; k < arr.length; k++) {
num *= arr[k];
}
console.log(num);

输出为



数组为: [
2, 3, 2, 5, 1, 7, 2,
3, 1, 11, 1, 13, 1, 1,
2, 17, 1, 19, 1
]
最小倍数为: 232792560
[Done] exited with code=0 in 0.219 seconds




第六题 *方的和与和的*方之差

前十个自然数的*方的和是:
12+ 22 + … + 102 = 385
前十个自然数的和的*方是:
(1 + 2 + … + 10)2 = 552 = 3025
因此前十个自然数的*方的和与和的*方之差是 3025 ? 385 = 2640。
求前一百个自然数的*方的和与和的*方之差。


var squares = 0;
var sum = 0;
for (var i = 1; i <= 100; i++) {
sum += i * i;
squares += i;
}
console.log("*方和:" + sum, ",", "和的*方:" + squares * squares);
console.log("差:", squares * squares - sum);

输出为



*方和:338350 , 和的*方:25502500
差: 25164150
[Done] exited with code=0 in 0.154 seconds




第七题 第10001个素数

列出前6个素数,它们分别是2、3、5、7、11和13。我们可以看出,第6个素数是13。
第10,001个素数是多少?


var i = 2;
var index = 0;
while (true) {
var flag = true;
for (let j = 2; j < i; j++) {
if (i % j === 0) {
flag = false;
break;
}
}
if (flag) {
index++;
}
i++;
//当第10001个素数时,打印此时的值,但是别忘记-1,
//同时退出循环
if (index === 10001) {
console.log(i - 1);
break;
}
}

输出为



104743
[Done] exited with code=0 in 2.453 seconds




第八题 连续数字最大乘积

在下面这个1000位正整数中,连续4个数字的最大乘积是 9 × 9 × 8 × 9 = 5832。


73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450


找出这个1000位正整数中乘积最大的连续13个数字。它们的乘积是多少?


var str =
"73167176531330624919225119674426574742355349194934"
+"96983520312774506326239578318016984801869478851843"
+"85861560789112949495459501737958331952853208805511"
+"12540698747158523863050715693290963295227443043557"
+"66896648950445244523161731856403098711121722383113"
+"62229893423380308135336276614282806444486645238749"
+"30358907296290491560440772390713810515859307960866"
+"70172427121883998797908792274921901699720888093776"
+"65727333001053367881220235421809751254540594752243"
+"52584907711670556013604839586446706324415722155397"
+"53697817977846174064955149290862569321978468622482"
+"83972241375657056057490261407972968652414535100474"
+"82166370484403199890008895243450658541227588666881"
+"16427171479924442928230863465674813919123162824586"
+"17866458359124566529476545682848912883142607690042"
+"24219022671055626321111109370544217506941658960408"
+"07198403850962455444362981230987879927244284909188"
+"84580156166097919133875499200524063689912560717606"
+"05886116467109405077541002256983155200055935729725"
+"71636269561882670428252483600823257530420752963450";

var arr = str.split("");
var arr1 = arr.map(function(value) {
return parseInt(value);
});
var mul = [];
for (var i = 0; i < arr1.length; i++) {
if (arr1[i] == 0) {
continue;
}
var num =
arr1[i] *
arr1[i + 1] *
arr1[i + 2] *
arr1[i + 3] *
arr1[i + 4] *
arr1[i + 5] *
arr1[i + 6] *
arr1[i + 7] *
arr1[i + 8] *
arr1[i + 9] *
arr1[i + 10] *
arr1[i + 11] *
arr1[i + 12];
mul.push(num);
if (i === arr1.length - 13) {
break;
}
}
mul.sort(function(a, b) {
return b - a;
});
console.log("13位数最大连乘积", mul[0]);

输出为



13位数最大连乘积: 23514624000
[Done] exited with code=0 in 0.239 seconds



PS: 我是个渣渣,想不出优雅的写法,唉。。。



第九题 特殊毕达哥拉斯三元组

毕达哥拉斯三元组是三个自然数a < b < c组成的集合,并满足a2 + b2 = c2
例如,32 + 42 = 9 + 16 = 25 = 52
有且只有一个毕达哥拉斯三元组满足 a + b + c = 1000。求这个三元组的乘积abc。


var flag = false;
for (var a = 1; a < 1000; a++) {
for (var b = a + 1; b < 1000; b++) {
for (var c = b + 1; c < 1000; c++) {
if (a + b + c == 1000 && a * a + b * b == c * c) {
console.log("a:", a, " b:", b, " c:", c);
console.log("abc:", a * b * c);
flag = true;
break;
}
}
if (flag) {
break;
}
}
if (flag) {
break;
}
}

输出为



a: 200 b: 375 c: 425
abc: 31875000
[Done] exited with code=0 in 0.272 seconds




第十题 素数的和

所有小于10的素数的和是2 + 3 + 5 + 7 = 17。
求所有小于两百万的素数的和。
分析:考虑提高性能,使求解速度快。一是使用break,只要满足有解就退出小循环;二是使用Math.sqrt,只需要算一半就行


var sum = 0;
var num = 2000000;
for (let i = 2; i < num; i++) {
let flag = true;
for (let j = 2; j <= Math.sqrt(i); j++) {
if (i % j == 0) {
flag = false;
break;
}
}
if (flag) {
sum += i;
}
}
console.log(sum);

输出为



142913828922
[Done] exited with code=0 in 1.008 seconds




持续更新中…



友情链接: