Gap In Primes

2017-05-05

这两天在codewars上面刷题，遇到了这个题，题目意思是让你完成一个函数，这个函数有三个参数，分别是 g，m，n。你需要做的是找到 [m,n] 之间的所有素数，并且相邻的两个素数之差要等于 g，如果有满足条件的组合，则返回；否则，返回null。

这个题目乍一看上去没什么毛病，直接上代码：

function gap(g, m, n) {
    let arr = [];
    //将所有偶数剔除，不添加至数组中
    if (m % 2 === 0) {
        m = m + 1;
        while (m <= n) {
            arr.push(m);
            m += 2;
        }
    } else {
        while (m <= n) {
            arr.push(m);
            m += 2;
        }
    }
    //过滤所有素数
    arr = arr.filter((element, index, array) => {
        let start = 2;
        while (start <= Math.sqrt(element)) {
            if (element % start++ < 1) {
                return false;
            }
        }
        return element > 1;
    });
    //找到符合条件的组合
    for (let i = 0; i < arr.length - 1; i++) {
        if (arr[i] + g === arr[i + 1]) {
            return [arr[i], arr[i + 1]];
        }
    }
    return null;
}

所有的基础测试用例都通过了，random test 也通过了，可是就毁在效率上了。（心累）

自己想了想，没有什么优化思路，还是上网去查查资料吧。结果发现一个大神给出的优化思路：

Don’t use array to store prime numbers. You only need one previous prime to remember. And even if you ever do this, don’t remove elements from its middle, as shifting array contents is very costly.（第一个建议第一句话就是不要使用数组来存储素数，多么痛的领悟。最后又提到：转化数组的内容是恨消耗性能的。）
Store number from expensive Math.sqrt(), don’t re-calculate it every iteration. Basically, this is rule for every loop - precalculate limits if possible.（使用 Math.sqrt() 这个函数，不要每次迭代的时候重新计算）
…

看看大神给出的高效率的解法：

function gap(gap, start, end) {
    //cut off odd gaps
    //bitwise AND can test least significant bit
    //odd numbers have 1, even have 0
    if (gap & 1) { //is it odd?
        if (start > 2 || end < gap + 2) return null; //check if 2 is in range
        return isPrime(gap + 2) ? [2, gap + 2] : null; //check additionally the other part
    }
    var previous = null; //no initial value
    //loop over odd numbers to check for primes
    for (var current = start | 1; //set last bit to 1: /odd numbers stay same, even numbers become next odd
    current <= end;
    current += 2 // skip any even number
    ) {
        if (isPrime(current)) {
            if (current - previous === gap) //is it a match?
                return [previous, current];
            //no need for "else" here as the other branch has "return"
            previous = current; // anyway, save it
        }
    }
    return null; //no early return from loop = nothing matches
    /**
        Tests if n is prime
    */
    function isPrime(n) {
        if (n <= 6) //cut away small primes explicitly
            return n === 2 || n === 3 || n === 5;
        //cut away small divisors (2 and 3) explicitly
        if (n & 1 === 0 || //using bitwise AND for even numbers
        n % 3 === 0) return false;
        var limit = Math.floor(Math.sqrt(n)); //precalculate loop limit
        // loop is checking every divisor using 6k ± 1 pattern
        for (var t = 5; //start with 5, first 6k - 1 number
        t <= limit;
        t += 6 //step by 6
        ) {
            if (n % t === 0 || //6k - 1
            n % (t + 2) === 0) //6k + 1
            return false;
        }
            return true;
        }
    }
console.log(""); //this makes console output timestamp
console.log("gap(8,3000000,4000000)", "->", gap(8,3000000,4000000)); // ~5ms
console.log("gap(120,3000000,4000000)", "->", gap(120,3000000,4000000)); // ~600ms

这个解题思路需要好好的消化下！

附：传送门