“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 = 7
Output: 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.