Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

计数质数 #161

Open
louzhedong opened this issue Jun 25, 2019 · 0 comments
Open

计数质数 #161

louzhedong opened this issue Jun 25, 2019 · 0 comments

Comments

@louzhedong
Copy link
Owner

习题

出处 LeetCode 算法第204题

统计所有小于非负整数 n 的质数的数量。

示例:

输入: 10
输出: 4
解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

思路

遍历统计

关键点:计算j的质数,只要计算从2到i的整数能否整除j。其中i * i <= j。可以减少很多的计算量

解答

var countPrimes = function (n) {
  if (n < 3) return 0;
  var count = 1;

  for (var i = 3; i < n; i  ) {
    var flag = true
    for (var j = 2; j * j<= i; j  ) {
      if (i % j == 0) {
        flag = false;
        break;
      }
    }
    if (flag) {
      count  ;
    }
  }
  return count;
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant