javascript - Erroneous output in printing prime numbers

Question

The code incorrectly computes many non-prime numbers as prime, and I am not sure why. Basically the output alternates "prime" and "not prime" for the input.

#!/usr/bin/env node

for (var i = 3; i <= 30; i++) {
  console.log(i + ": " + isPrime(i) + " ");
}

function isPrime(num) {
  var counter;

  for (counter = 2; counter < num; counter++) {
    if(num % counter == 0) {
      return "not prime";
    }
    else {
      return "prime";
    }
  }
}

Answer 1

for (var i = 3; i <= 30; i++) {
  console.log(i + ": " + isPrime(i) + " ");
}

function isPrime(num) {
  var counter;

  for (counter = 2; counter < num; counter++) {
    if(num % counter == 0) {
      return "not prime";
    }
  }
  // only return that it is prime if it is not evenly
  // divisible by all numbers less than it
  // (technically you only need to check up to sqrt(num) + 1)
  return "prime";
}

Answer 2

您需要在循环之后返回 true，而不是在循环内。例如，数字是 9。第一次迭代 if(9%2 == 0)-false 否则返回素数。但九不是素数。只有在您通过迭代后才返回 true 并且您会找到预期的结果。

function isPrime(num) {
var counter;

for (counter = 2; counter < num; counter++) {
if(num % counter == 0) {
  return " not prime";
}
}
  return " prime";
}

Answer 3

小提琴

循环完成后，您必须返回素数

for (var i = 3; i <= 30; i++) {
  console.log(i + ": " + isPrime(i) + " ");
}

function isPrime(num) {
  var counter;

  for (counter = 2; counter < num; counter++) {
    if(num % counter == 0) {
     return "not prime";
    }
  }
  return "prime";

}

Answer 4

num % 2 is num mod 2, which just means the remainder of the number after being divided by two.

What you would really like to do is something like this:

primes = [2]
for (var i=0;i<primes.length;i++){
    if (primes[i]<sqrt(num)){
        if (num % primes[i] == 0){
            console.log("Not prime!");}
        }
    else{
        console.log("prime!");
        primes.push(num);
    }
}

When you're determining primes, you should only be trying to construct the prime factorization of the number you're checking, otherwise you're doing FAR more work than you should be doing. Since the prime factorization is by definition constructed of primes, those are the only numbers you should check for modularity.

Additionally you should only check up to the square root of the number because any number that it is divisible by will have a matching number. Examples:

104 = 57*2
39 = 13*3

Complexity goes from O(n) to O(log(sqrt(n)) which is 4 comparisons instead of 100 even at an n of just 100 and it just keeps getting better.

Answer 5

the first time something misses your f(num % counter == 0) condition, it will return as not prime

the easiest thing to take your return "prime"; call out of your for-loop

function isPrime(num) {
    for(counter = 2; counter < num; counter++) {

        if(num % counter == 0) {
            return "not prime";
        }
    }
    return "prime";
}