javascript - 编程，算法的问题

问题描述

前天面试了一个问题请使用js,python,java,c,c++之类的语言，在10秒内计算出100亿的数据，并且（只能在3秒内）完成，偶数在奇数前格式如下1，2，3，4，5输出结果是2，1，4，3，6，5，问题2：在1的代码之上，要求不能使用for while关键字，从100亿里面取所有的质数（时间不能超过3秒）这个怎么搞？

问题解答

第一个问题没看懂，是说2个数字为一对，然后偶数在奇数前面？

第二个问题简单啊，不能用循环，那就用数组迭代呗。

话说 php 的 foreach 算么（笑

我觉得面试官的意图是让你写一个递归函数？嗯估计是。

前天面试了一个问题请使用js,python,java,c,c++之类的语言，在10秒内计算出100亿的数据，并且（只能在3秒内）完成，偶数在奇数前格式如下1，2，3，4，5输出结果是2，1，4，3，6，5，问题2：在1的代码之上，要求不能使用for while关键字，从100亿里面取所有的质数（时间不能超过3秒）这个怎么搞？

那么递归性能不太够。。。但是我还是用了一些。。 For Performance

。。。 100亿 的体量 应该是有的。 我还没发现。

100 亿有点大啊 我先 10 万了

var n = 1000 * 1000; var test = new Array(n).fill(n).map((e, idx) => idx);

这样可以获得到 10 万长度的数组 自然数。

偶数在前 奇数在后

观察之后发现，奇数 + 1、 偶数 - 1 就可以了

var isEven = n => n % 2 === 0; var res001 = test.map((e, idx) => { if (isEven(e)){return e - 1; } else {return e + 1; }});

完成第一个问题

下一个问题是在上面的基础上取得质数 即从 zs 里取得所有质数

查了一下关于质数的问题，别人说 质数分布在 6 的倍数的左边或者右边 那么我只要遍历 每一个6的倍数的左边和右边 并判断他们是不是质数即可。

链接： 判断一个数是否为质数/素数——从普通判断算法到高效判断算法思路

// 剔除第一个负数 var zs = res001.slice(1); var is6x = n => n % 6 === 0; var isPrime = n => { let temp = Math.sqrt(n); for(let i = 2; i <= temp; i++){ if(n % i === 0){ return false; } } return true; } var lasts = zs.filter(is6x).reduce((acc, cur) => { let left = cur - 1, right = cur + 1; if (isPrime(left)) acc.push(left); if (isPrime(right)) acc.push(right); return acc; }, []); console.log(lasts); ScreenShot Two

不知道对不对 ...

不过还需要把 小于 6 的质数 1 2 3 5 单独拼回去。 （这里没拼）

把上面写的代码黏起来

var isEven = n => n % 2 === 0; var is6x = n => n % 6 === 0; var isPrime = n => { let temp = Math.sqrt(n); for(let i = 2; i <= temp; i++)if(n %i== 0){ return false; } return true; } function timeTest(n){ var test = new Array(n).fill(n).map((e, idx) => idx); var res001 = test.map((e, idx) => {if (isEven(e)){ return e - 1; } else { return e + 1; } }); var zs = res001.slice(1); var lasts = zs.filter(is6x).reduce((acc, cur) => {let left = cur - 1, right = cur + 1; if (isPrime(left)) acc.push(left); if (isPrime(right)) acc.push(right); return acc; }, []); return lasts; }

test

var n = 1000 * 10000; console.time(’1000 万’)timeTest(n); console.timeEnd(’1000 万’);

1000 万 结果如图

花了 13.8 秒 不可能做到 10 + 3 秒内完成 100亿 的体量。

我的电脑是 i5-4210M 12G Chrome 58

JavaScript 做不到这样的性能： 100亿 个数字 13 秒内 ....

好几个 G 的数据 ......

按照上面的思路来做，即使是 C/C++ 估计也很难13秒跑完100亿。

解决问题为主。

判断一个数是否为质数/素数——从普通判断算法到高效判断算法思路

首先感谢楼上的求质数的算法，我贴下我的结果和代码（只有1000万，一亿浏览器直接炸掉了，而且求质数那里不能用递归（我测试的结果），不然也得炸，只能迭代）。

浏览器里面的结果：

node里面的结果：

var arr = [];console.time('1000万');for( var i = 1; i <= 10000000; i++ ){ arr.push(i);}for( var j = 0, len = arr.length;j < len; j+=2 ){ arr[j]++; arr[j+1]--;}function isPrime(num,sqrt){ if(num == 1) return false; if(num == 2 || num == 3 ) return true; if(num % 6 != 1 && num % 6 != 5) return false; var tmp = sqrt(num); for(var i= 5;i<=tmp; i+=6 ) if(num % i == 0 || num % ( i + 2) == 0 ) return false ; return true; };function getPrime(sourceArray,array,isPrime,sqrt){ sourceArray.map(function(num,idx){if(isPrime(num,sqrt)){ array.push(num);} }); return array;};var result = getPrime(arr,[],isPrime,Math.sqrt);console.timeEnd('1000万');