2020-05-18 5 kyu Gap in Primes

https://www.codewars.com/kata/561e9c843a2ef5a40c0000a4/javascript

My answer / AC

function gap(g, m, n) {
    var between = false;
    for(let i=m; i<=n-g; i++){
      if(isPrime(i) && isPrime(i+g)){
        for(let j=i+1; j<i+g; j++){
          if(isPrime(j)) { between = true; }
        }
        if(between) {
          between = false;
          continue;
        }
        return [i, i+g];
      }
    }
    return null;
}

/*
function isPrime(num) {
  for(var i=2; i<num; i++){
    if(num%i === 0) return false;
  }
  return num>1;
}
*/
const isPrime = num => {
    for(let i = 2, s = Math.sqrt(num); i <= s; i++)
        if(num % i === 0) return false; 
    return num > 1;
}

一开始用的是注释里的isPrime()，但是由于这个是从2到num的，导致复杂度过高。转化为2到Math.sqrt(num)就能通过了。BA里面的实践也是类似的，只不过他没用Math库，把循环条件定为了i*i<=x

Best answer

function gap(g, m, n) {
    var lastPrime = 0;
    var isPrime = function(x) { 
      for (var i=2; i*i<=x; i++) { if (x % i == 0) return false; } return true;
    }
    
    for(var i = m; i <= n; i++)
        if(isPrime(i)) {
            if(i - lastPrime == g) return [lastPrime, i];
            else lastPrime = i;
        }
      
    return null;
}

好在哪里？

• 中间变量lastPrime用来缓存最近一个质数，这样就能够避免两个质数中间有别的质数，并省掉循环、减少复杂度

Recap

学会判断质数的写法没？