Javascript Prime number generator

Question

I am trying to generate the first prime numbers that are less than 20 (the only way I know how to do it with my limited knowledge):

let arr = [];

for (let x = 3; x <= 20; x++) {
  for (let i = 20; i > 0; i--) {
    if (x % i !== i) {
      arr.push(x)
    }
  }
  console.log(arr)
}

I do want to preface by saying there is WAY more efficient methods out there, but I am trying to just do things by scratch and learn to be more efficient, rather than someone just tell me.

The intention of the code:

An outer loops that will start at 3, go to 20, increment by 1
An inner loop that will start at 20, go to 0, and decrement by 1.
condition in the inner-loop: If the number x modulo the range of numbers i and it returns i, it is therefor not a prime.

Example:

7 is prime.

7 % 7 = 0
7 % 6 = 1
7 % 5 = 2
7 % 4 = 3
7 % 3 = 4
7 % 2 = 5
7 % 1 = 6

whereas

6 is not prime

6 % 6 = 0
6 % 5 = 1
6 % 4 = 2
6 % 3 = 3    <=== because of this
6 % 2 = 4
6 % 1 = 5

the output is 20 multiples of the the range of numbers from 3-20. i.e., 3,3,3,3,3,........20,20,20.....

no need to increment by 1, you can increment by 2 (even numbers are not prime) — depperm, Dec 30 '22 at 15:55
Yep, I am fixing that right now, I had the wrong idea about what Modulu was — Raboush2, Dec 30 '22 at 16:05

score 3 · Answer 1 · answered Dec 30 '22 at 17:01

Understanding the OP cares more about clarity than efficiency, there's one simple observation that reduces the search significantly and doesn't add much (really, any) complexity: a non-prime must have a prime divisor, so we can restrict the divisibility check to smaller primes that were already found.

Written simply...

let arr = [];

for (let x = 3; x <= 20; x++) {
  // check only the previously found primes
  let isPrime = true;
  for (let i = 0; i < arr.length; i++) {
    if (x % arr[i] === 0) {
      isPrime = false;
      break;
    }
  }
  if (isPrime) arr.push(x)
}

console.log(arr)

Written tersely...

let primes = [];

for (let x = 3; x <= 20; x++) {
  if (primes.every(prime => x % prime !== 0)) primes.push(x)
}

console.log(primes)

Do you try your hand at code golf? – JosephDoggie Dec 30 '22 at 17:05 — JosephDoggie, Dec 30 '22 at 17:05

score 2 · Answer 2 · answered Dec 30 '22 at 16:06

So there are a few flaws in the logic. There are a few ways to optimize the code and to fix the logic.

the outer loop can increment by 2 (evens aren't prime)
the inner loop doesn't need to start larger than x instead start x-1 and go to 1
add a flag (np not prime) to track if number isn't prime
- if x % i is 0, then flag np and break (if some num (x) is divisible(mod ...===0) by smaller number(i) it isn't prime)
- only add x if !np (or prime)
- reset the flag for each x

let arr = [];
let np=false
for (let x = 3; x <= 20; x+=2) {
  np=false
  for (let i = x-1; i > 1; i--) {
    if (x % i === 0) {
      np=true
      break
    }
  }
  if(!np){
    arr.push(x)
  }
}
console.log(arr)

Javascript Prime number generator

2 Answers2