Is It Prime?

So, I’ve been diving into this prime number challenge and it’s pretty interesting! First off, we know a prime number is like, any integer greater than 1 that can’t be formed by multiplying two smaller integers, right? But when the numbers get big, it’s a whole different game!

Here’s my thought process for creating a function to check if a number is prime:

1. Start by checking if the number is less than 2. If it is, return false since 0 and 1 aren’t prime.
2. If the number is 2, return true because 2 is prime!
3. For any even number greater than 2, return false since they can be divided by 2.
4. Now, for odd numbers greater than 2, you only need to check divisibility up to the square root of the number. This is like, way faster than checking all the way up to the number itself.
5. Loop through all odd numbers starting from 3 to the square root of the number and check if any of them divide the number evenly. If you find one, then it’s not prime!

Here’s some pseudo code to wrap this up:

function isPrime(n) {
    if (n < 2) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;

    for (let i = 3; i * i <= n; i += 2) {
        if (n % i == 0) return false;
    }
    return true;
}
    

Edge cases like 0 and 1 are covered by that first if statement. But what if we hit a mega big prime number? This method should still be efficient since we’re only looping up to the square root.

Optimizing might be tricky, but really thinking about how many times we’re looping through can save a lot of time when we deal with big numbers. Maybe even using some sieving techniques if we need to check a range of numbers? Just a thought!

Let me know your thoughts! I’m super curious about what other tricks you might come up with for this challenge!