問題描述

前天面試了一個問題請使用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萬');