Javascript:数字素数测试

Question

我正在尝试完成代码检查挑战,要求您检查数字是否为素数.无论出于何种原因,我的解决方案似乎不适用于奇素数的平方(例如9返回true而不是false).

function isPrime(num) {

  if (num === 2) {
    return true;
  }
  else if(num > 1){
    for (var i = 2;  i < num; i++) {

      if (num % i !== 0 ) {
        return true;
      }

      else if (num === i * i) {
        return false
      }

      else {
        return false;
      }
    }
  }
  else {
    return false;
  }

}

console.log(isPrime(121));

Ps我包括第二个else/if语句,因为我试图解决问题.

Answer 1

尽可能简单:

function isPrime(num) {
  for(var i = 2; i < num; i++)
    if(num % i === 0) return false;
  return num > 1;
}

使用ES6语法:

const isPrime = num => {
  for(let i = 2; i < num; i++)
    if(num % i === 0) return false;
  return num > 1;
}

您也可以从降低算法的复杂度O(n),以O(sqrt(n))如果您运行的循环,直到一些平方根:

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

Answer 2

这里有一个小小的建议,你为什么要为整个n个数运行循环？

如果一个数字是素数,它将有2个因子(1和数字本身).如果它不是素数,它们将有1,数字本身等等,你不需要运行循环直到数字,可能你可以考虑运行它直到数字的平方根.

你可以通过欧拉的主要逻辑来做到这一点.检查以下代码段:

function isPrime(num) {
  var sqrtnum=Math.floor(Math.sqrt(num));
    var prime = num != 1;
    for(var i=2; i<sqrtnum+1; i++) { // sqrtnum+1
        if(num % i == 0) {
            prime = false;
            break;
        }
    }
    return prime;
}

现在复杂度是O(sqrt(n))

更多信息 为什么我们检查素数的平方根以确定它是否是素数？

希望能帮助到你

Answer 3

酷版:

const isPrime = n => ![...Array(n).keys()].slice(2).map(i => !(n%i)).includes(true) && ![0,1].includes(n)

Answer 4

function isPrimeNumber(n) {
  for (var i = 2; i < n; i++) { // i will always be less than the parameter so the condition below will never allow parameter to be divisible by itself ex. (7 % 7 = 0) which would return true
    if(n % i === 0) return false; // when parameter is divisible by i, it's not a prime number so return false
  }
  return n > 1; // otherwise it's a prime number so return true (it also must be greater than 1, reason for the n > 1 instead of true)
}

console.log(isPrimeNumber(1));  // returns false
console.log(isPrimeNumber(2));  // returns true
console.log(isPrimeNumber(9));  // returns false
console.log(isPrimeNumber(11)); // returns true

Answer 5

function isPrime(num) {
  if (num <= 1) return false; // negatives
  if (num % 2 == 0 && num > 2) return false; // even numbers
  let s = Math.sqrt(num); // store the square to loop faster
  for(let i = 3; i <= s; i++) { // start from 3, stop at the square, increment
      if(num % i === 0) return false; // modulo shows a divisor was found
  }
  return true;
}

Answer 6

质数的形式为 6f ± 1，不包括 2 和 3，其中 f 是任何整数

 function isPrime(number)
 { 
   if (number <= 1)
   return false;

   // The check for the number 2 and 3
   if (number <= 3)
   return true;

   if (number%2 == 0 || number%3 == 0)
   return false;

   for (var i=5; i*i<=number; i=i+6)
   {
      if (number%i == 0 || number%(i+2) == 0)
      return false;
   }

   return true;
 }

解的时间复杂度：O(sqrt(n))

Answer 7

// A list prime numbers

function* Prime(number) { 
  const infinit = !number && number !== 0;
  const re = /^.?$|^(..+?)\1+$/;  
  let actual = 1;
 
  while (infinit || number-- ) {
      if(!re.test('1'.repeat(actual)) == true) yield actual;
      actual++
  };
};

let [...primers] = Prime(101); //Example
console.log(primers);