Skip to content

Latest commit

 

History

History
95 lines (62 loc) · 3.58 KB

120.md

File metadata and controls

95 lines (62 loc) · 3.58 KB

Solution

Submission link - https://bigfrontend.dev/problem/isPrime/discuss/239

/**
 * @param {number} num - positive integer
 */
function isPrime(num) {

  // Wait! What? We need square root here? 🤔
  // Yes, I had same question. I wrote detailed explanation below.
  const squareRootOfNum = Math.floor(Math.sqrt(num));

  let prime = num > 1;

  for(i = 2; i <= squareRootOfNum; i++) {
    if(num % i === 0) {
      prime = false;
      break;
    }
  }
  return prime;
}

Short story

Let me tell you the truth. I thought it would be easy to think and solve the problem. I did know about prime numbers but didn't know how do you identify for a given number num.

I searched on StackOverflow and found that someone has posted a solution but its time complexity was O(num). It means that you need to iterate num times.

This is not good if you have 1 million as num. It means you will iterate 1,000,000 times if you need to identify whether 1,000,000 is a prime number or not. 😱

I then searched for algorithms and found a few on Wikipedia but they were too advance for solving problems for interviews. I found one more post on StackOverflow mentioning about square root and it can make time complexity to O(sqrt(n)) which is a huge win.

I realized this win when I compared solutions (num = 1114111) using square root and without it.

[A] Iterate till Math.sqrt(num) - 0.775 ms

[B] Iterate till num - 101.110 ms

Difference: Solution [A] is 99.233% faster than Solution [B]

Algorithm -

Let's first see the definition. A number is prime if and only if it is divisible by 1 and itself provided that it is a positive number greater than 1. Examples - 2, 5, 7, 11

So a number can't be prime if it is a multiplication of two factors (one of the factors should be less than or equal to Math.sqrt(num)).
if n = a * b is true then it isn't a prime number provided a or b should be less than Math.sqrt(num)

Example- 8 = 2x4 (not a prime number as 2 and 4 gives 8, here factor 2 is equal to Math.sqrt(8) => Math.floor(2.8284271247461903))

In simple terms, a non-prime number will have at least 3 factors -

  • Divide by self
  • Divide by 1
  • One more factor

So our job is to find that one more factor. We can do by checking if the number from 2 to till Math.sqrt(num) has remainder 0.

  1. Get the square root of num.
  2. Begin loop by 2 and end at equal or less than the square root of num
  3. if the remainder is 0 then it is a non-prime number else it is a prime number

Code overview -

  • We first calculate the square root of num using the Math.sqrt method. Math.sqrt(num)

  • We use Math.floor to round off decimal so for loop behave and compare realistically Math.floor(Math.sqrt(num));

  • We create a prime variable and check if it is greater than 1. This is useful when for-loop provide doesn't provide anything.

  • We check if prime > 1 means there was no change in the prime variable by for-loop and if it is greater than 1 means prime else other numbers (< 1) are non-primes (1, 0 or negatives or any other)

  • We return the prime variable and whoa! we are done.

Resources -

  1. https://stackoverflow.com/questions/40200089/number-prime-test-in-javascript
  2. https://stackoverflow.com/a/5811176/4007898
  3. https://stackoverflow.com/a/40200212/4007898

Note: Few things are simplified here for solving the problem and doesn't mean that it is exactly how done in maths or computer program.

Excited to hear your "Hello" on Twitter (@knowkalpesh)