Today to share a relatively simple, but more fun topic — looking for a certain range of prime numbers

At the first sight of this topic, we must think: such a simple topic, is it necessary to share with you?

Please also take such questions, continue to look down deeply.

1. First edition: Double loop

See such a topic, we will certainly think of the first time to double cycle solution, not busy, first to a small chestnut to see

Chestnut: 🌰

function findPrimeNumbers (n) {
  const result = []
  for (let i = 4; i < n; i++) {
    let status = false
    for (let j = 2; j < i; j++) {
      if (i % j === 0) {
        status = true
        break}}if(! status) { result.push(i) } }return result
}
Copy the code

OK, so we’re done with this problem, so let’s verify it.

1. Look for100The number of primes within.
findPrimeNumbers1(100) 
/* [5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97] */
Copy the code

And here we can see that the logic is fine, it filters out normally.

2. Look for10000Prime number within
findPrimeNumbers1(10000)
/* [5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, ... 1127 more items ] */
Copy the code

There’s nothing wrong with that, you can look it up, right

3. Look for1000000Problems within
findPrimeNumbers1(1000000)
Copy the code

Here, when we run the program, we find a problem, it doesn’t complete for a long time.

So this program causes a timeout error.

2. Second edition: Optimization of the double cycle

Some of you might say, well, if I say, well, this is an even number I’m not going to check it, I’m just going to skip it. Will it improve performance?

OK, so let’s verify that

Chestnut: 🌰

function findPrimeNumbers (n) {
  const result = []
  for (let i = 4; i < n; i++) {
    let status = false
    if (i % 2= = =0) continue // Add this line of code
    for (let j = 2; j < i; j++) {
      if (i % j === 0) {
        status = true
        break}}if(! status) { result.push(i) } }return result
}
Copy the code

After the verification of the above three numbers 100, 10000 and 1000000, we can find a problem. We still cannot find the quantity within 1000000.

3. Version 3: Optimize queries again

At this point, many students are probably at a loss, since you can’t find a prime number within 1000000, so don’t check. Why embarrass yourself.

Pretty good, deep feeling – take a step back the vast sky and the sea this truth.

Well, problems have to be solved. In case you ever need it.

Well, without further ado, let’s look at the implementation of version 3.

Chestnut: 🌰

function findPrimeNumbers (n) {
  const arr = new Array(n).fill(1)
  for (let i = 2; i < n; i++) {
    if (arr[i]) {
      for (let j = 2; i * j < n; j++) {
        arr[i * j] = 0}}}let result = []

  for (let i = 0, len = arr.length; i < len; i++) {
    if (arr[i]) {
      result.push(i)
    }
  }

  return result
}
Copy the code

After verifying the numbers 100, 10000 and 1000000, we found that we could find primes within 1000000.

Now let’s explain the implementation.

Explanation:

  • First, create a length ofnArray and use1Filled in.
  • Iterate over the array if the current value is1, all the multiples of the current value are changed to0
  • When the traversal is complete, the value in the lookup array is1The index. Add to the result and return.

This question is simple and easy to understand, but it’s really fun, so share it with you.

That’s all for today

Bye~