javaScript打印n以内的素数——试除法及优化

试除法

//打印n以内的质数
//素数：只能被1和它本身整除
function printPrimes(target) {
  for (let i = 2; i <= target; i++) {
    let count = 0;
    for (let j = 2; j <= Math.sqrt(i); j++) {
      if (i % j === 0) {
        count++;
        break;
      }
    }
    if (count == 0) {
      console.log(i);
    }
  }
}
printPrimes(1000);

 试除法优化

function printPrimes(target) {
  let isPrime = new Array(target + 1).fill(true);
  isPrime[0] = false;
  isPrime[1] = false;

  for (let i = 2; i <= Math.sqrt(target); i++) {
    if (isPrime[i]) {
      for (let j = i * i; j <= target; j += i) {
        isPrime[j] = false;
      }
    }
  }

  for (let i = 2; i <= target; i++) {
    if (isPrime[i]) {
      console.log(i);
    }
  }
}

printPrimes(1000);