What's the most efficient prime-finding algorithm? (Week 1 Practice Problems)

Question

In the Prime practice problem, there's a thought question that says:

Can you make the prime-finding algorithm more efficient than checking if a number is divisible by every number between 2 and 1 less than itself? Can you think of another way to generate prime numbers?

Here's what I came up with:

    bool prime(int number)
{
    if (number == 2 || number == 3 || number == 5)
    {
        return true;
    }
    else if (number == 1 || number % 2 == 0 || number % 3 == 0 || number % 5 == 0)
    {
        return false;
    }
    else
    {
        return true;
    }
}

I'm still pretty new to programming, so I don't really know how to make a piece of code more efficient. What do you think about my solution? Is it more efficient than using a loop?

Answer 1

You can likely google it to find out. But the first thing that comes to mind is to lower the high limit of numbers to check. Simply put, if you're checking whether N is a prime, you need only see if it is divisible by numbers between 2 and the square root of N.

No need to go any higher. If a number can be evenly divided by something greater than it's square root, then it can also be divided by another number that's less than the square root.

As for your code, see what happens with 49. ;-) You can break that code easily by applying it to the square of the first prime beyond all the prime numbers used in the code. There is no known formula for determining if a number is prime, except by trial and error.

So far, The largest known prime number (as of June 2023) is 282,589,933 − 1, a number which has 24,862,048 digits when written in base 10. It was found via a computer volunteered by Patrick Laroche of the Great Internet Mersenne Prime Search (GIMPS) in 2018.