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

第 85 期(算法-数学):判断一个数是否为素数(质数) #88

Open
wingmeng opened this issue Aug 13, 2019 · 0 comments
Open

Comments

@wingmeng
Copy link
Collaborator

数学中素数又称质数,指整数在一个大于1的自然数中,除了1和该整数自身外,无法被其他自然数整除的数。换句话说,素数只有两个正因数:1和它自己。

如何判断一个整数是否为素数呢?根据上面的定义,我们一般会想到用试除法,即遍历从2到该整数的所有整数,挨个拭除,如果因数个数小于2,则为素数,代码如下:

// 简单粗暴的试除法
function isPrime(num) {
  if (num <= 1) return false;

  var result = [];

  for (var i = 2; i <= num; i++) {
    if (num % i === 0) {
      result.push(i);
    }
  }

  return result.length < 2;
}

上面的算法比较简单粗暴,但是效率是最差的,时间复杂度 O(n) 。仔细观察会发现:一个数如果有(自身除外)质因数,其质因素肯定小于等于这个数的一半,所以我们不必一直遍历完所有数字,只需要循环到这个数的一半就可以了,优化后的代码如下:

// 拭除法进阶
function isPrime(num) {
  for (var i = 2; i < num / 2; i++) {
    if (num % i === 0) return false;  // 如果有因数,可以直接断定为非素数
  }

  return num < 2 ? false : true;
}

上面的算法将时间复杂度减少了一半,为 O(n/2)。因为一个整数的因数都是成对出现的,例如8的因数有:1和8,2和4,4和2,这些成对因数中,一个必然小于 √n,另一个必然大于 √n,所以可以继续优化代码如下:

// 平方根法
function isPrime(num) {
  for (var i = 2; i < Math.sqrt(num); i++) {
    if (num % i === 0) return false;
  }

  return num < 2 ? false : true;
}

上面的算法,时间复杂度为 O(√n)(?)。

还有一种更好的算法,我不是很懂,小伙伴们自行感受:

// 筛选法
function isPrime(num) {
  if (num <= 1) return false;
  if (!!~[3, 5, 7, 11].indexOf(num)) return true;
  if (num % 2 === 0 || num % 3 === 0) return false;

  for (var i = 5; i <= Math.pow(num, 0.5); i += 6) {
    if (num % i === 0 || num % (i + 2) === 0) {
      return false;
    }
  }

  return true;
}

本文参考自:https://www.cnblogs.com/caiminfeng/p/4805544.html

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