找出小于n的偶数个数？

Question

我必须找到小于或等于 n 且满足以下条件的偶数个数。任何偶数都可以写成 (2^p)*k，其中 p,k 是某个常数，同时假定 n 也是偶数，因此 n=(2^q)*m。现在有多少个小于等于n的偶数满足p>q?

Answer 1

好吧，我的第一个想法是用一个简单的解决方案来实现它，例如示例：

const n = 1232;

function getPow(n) {
  let tn = n, twoPow = 0;
  while (tn % 2 === 0) {
    tn /= 2;
    twoPow++;
  }
  return twoPow;
}

const basePow = getPow(n);

let result = 0;
for (let i = 2; i < n; i+=2) {
  const tmpPow = getPow(i);
  if (tmpPow > basePow) {
    result++;
  }
}

console.log(result);

但后来我意识到解决方案是所有 M 数字，其中 ((q+1)^2)*x < n 所以这将带您进入下一个公式，基本上就是解决方案：

const n = 1232;

function getPow(n) {
  let tn = n, twoPow = 0;
  while (tn % 2 === 0) {
    tn /= 2;
    twoPow++;
  }
  return twoPow;
}

console.log(Math.floor(n / (Math.pow(2 ,getPow(n) + 1))));

因为解决方案是O(log n)任何时间限制

找出小于n的偶数个数？

find the number of even number less than n?

math

sequence