Faster way to check if a number is a prime?

Question

I got this code that checks if a number is a prime:

public static bool isPrime(int num)
{
    if (num == 1) return false;
    if (num == 2) return true;

    int newnum = Math.Floor(Math.Sqrt(num));

    for (int i = 2; i <= newnum; i++) 
        if (num % i == 0) return false;

    return true;
}

Is there any better and faster way to check if a number is a prime?

[Possible duplicate](http://stackoverflow.com/a/1510186/1324033) — Sayse, Jul 10 '13 at 19:15
That is indeed the naive way to check a prime, there are other algorithms for this like http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes — Gray, Jul 10 '13 at 19:15
Computer Software Salesperson: 3 is prime, 5 is prime, 7 is prime, 9 will be prime in the next release,... Statistician: Let's try several randomly chosen numbers: 17 is a prime, 23 is a prime, 11 is a prime... Professor: 3 is prime, 5 is prime, 7 is prime, and the rest are left as an exercise for the student. Computational linguist: 3 is an odd prime, 5 is an odd prime, 7 is an odd prime, 9 is a very odd prime,... Psychologist: 3 is a prime, 5 is a prime, 7 is a prime, 9 is a prime but tries to suppress it,... — Michael Viktor Starberg, Jul 10 '13 at 19:31
Unsure why this was marked as a duplicate of 'Find Prime' when this author cleanly wanted to check if a number was a prime rather than iterate until a prime was found. I just finished answering this question on the 'so-called' duplicate thread, and then realized it is not actually a duplicate. — Kraang Prime, Aug 16 '16 at 23:14
This is a nice way to do it, but there are better methods, such as those in this page: [Primality Test](http://en.wikipedia.org/wiki/Primality_test) — Jashaszun, Jul 10 '13 at 19:17
My students copy these algorithms and they are really dirty programming. You should use `while (div < limit and number % div != 0) ++div;` the use of `for` with `return` is nasty style. — juanfal, Nov 14 '22 at 09:43
@juanfal That's very subjective, I could argue that `while` is the nasty style and since you didn't give a reason why, I will do the same. In the end they perform the same and likely compile to the same assembly, so It's up to readability and preference — Tofandel, Aug 16 '23 at 12:43
You said 'you didn't give a reason…'. Is it necessary? English. `for` means for, `while` means while. If you break a `for`, you shouldn't have said `for` in the first place, you are twisting the language, and making it more difficult to understand. It can be shorter for you to write, but is ugly. — juanfal, Aug 28 '23 at 10:36

Rick Davin · Accepted Answer · 2013-07-13T14:56:02.850

Yes there is. For one, you could check for 2 separately and then loop through only odd numbers. That would cut the search loop in half. There could be more elaborate things to do but basically that should answer your question.

UPDATED WITH CODE:

    public static bool IsPrime(int number)
    {
        if (number < 2) return false;
        if (number % 2 == 0) return (number == 2);
        int root = (int)Math.Sqrt((double)number);
        for (int i = 3; i <= root; i += 2)
        {
            if (number % i == 0) return false;
        }
        return true;
    }

There are many duplicate discussions on SO and plenty of links about various primality search methods. However, since the OP here has a method to check a signed 32-bit integer, and not something much larger like an unsigned 64-bit integer, then a quick check shows the truncated square root of int.MaxValue to be 46340. Since we are looping through only odd numbers that would result in a maximum loop of 23170 iterations, which in my opinion is quite fast as long as we are limiting the discussion to Int32. If the question revolved around UInt64, then other methods should maybe be investigated regarding faster.

The code above takes care of any int value, not just the special case of 1. Perhaps you have a NumericUpDown control that limits the inputs but I don't know that from just the function shown. One could argue that it would be more proper to throw an exception if the input number is < 2, but I skipped that 'feature' here.

All even numbers are checked before the main loop, not just 2 (a common mistake).

And while this could be homework (in July!!!), there are tons of links throughout the Internet that would have similar code so I am not doing someone's homework for them. Since my code was added days after the original post, the OP has had time to research and learn since then.

Using `i * i <= number` might be faster than using `Math.Sqrt` in some cases may warrant a benchmark — Tofandel, Aug 16 '23 at 12:33

Faster way to check if a number is a prime?

1 Answers1

Linked