# “Is Prime Number” Cheat Sheet javascript solution

The “Is prime” challenge is in the easy category and is a good start for understanding more challenging algorithms using integers and boolean as data types. I will focus on explaining a solution that works and O time and space complexity.

Challenge:

Write a function, isPrimeNumber, that takes in a number as an argument and returns a boolean.

Note:

// number num

// loop using square root

// return boolean true/false

Example:

`Input:  num = 7Output: true`

Explanation:

1. First, we check if the number is less than 2, in which case it’s not prime.
`if (num < 2) {`
`return false;`

2. Loop through all the integers from 2 up to half of the number.

`for (let i = 2; i <= Math.sqrt(num); i++)`

3. Check if the number is divisible by any of the integers in the loop (i.e., the remainder is 0).

`if (num % i === 0)`

4. If the number is divisible by any integer in the loop, then it’s not prime and we can stop checking.

`return false;`

5. if we make it through the loop without finding any divisors, then the number is prime.

`return true;`

# Solution:

`function isPrimeNumber(num) {  if (num < 2) {    return false;   }  for (let i = 2; i <= Math.sqrt(num); i++) {    if (num % i === 0) {      return false;     }  }  return true; }`

Time complexity:

• The time complexity of the loop that checks if the number is divisible by any integer up to half of the number is O(n/2) or simply O(n), where n is the number being checked.
• Therefore, the overall time complexity of the algorithm is O(n), which means that the time taken to run the algorithm increases linearly with the size of the input number.

Space complexity:

• The space complexity of the algorithm is constant, O(1), because we’re only using a fixed amount of memory to store the input number and a few variables used in the loop.
• Regardless of the size of the input number, the algorithm always uses the same amount of memory.

Conclusion

Overall, the algorithm has a time complexity of O(n) and a space complexity of O(1). This makes it an efficient solution for checking if a number is prime, particularly for smaller input sizes. However, for larger input sizes, more advanced algorithms may be needed to achieve better performance.

--

--

Lifelong learner , Full Stack Software Engineer.