A faster way to check if a number is prime?

Question

I got this code that checks if a number is 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 a better and faster way to check if a number is prime?

Answer 1

Yes there is. First, you can check for 2 separately, and then skip only odd numbers. This would shorten the search cycle in half. There may be more complex things, but basically this 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 recurring discussions on SO and many links about various primitive search methods. However, since the OP here has a method for checking a signed 32-bit integer , rather than something larger than an unsigned 64-bit integer, a quick scan shows the truncated square root of int. MaxValue will be 46340. Since we are sorting only the odd numbers, which will lead to a maximum loop of 23,170 iterations, which, in my opinion, is pretty fast, while we limit the discussion to Int32. If the question revolves around UInt64, then other methods should be investigated relatively faster.

In the above code, any int value is taken into account, and not just a special case of 1. Perhaps you have a NumericUpDown control that restricts input, but I don’t know what only from the function shown. It could be argued that it would be more correct to throw an exception if the input number is <2, but I missed this function here.

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

And although it can be homework (in July !!!), there are tons of links all over the Internet that will have similar code, so I do not do homework for them. Since my code was added a few days after the initial post, the OP managed to learn and learn from then on.

Answer 2

This is a good way to do this, but there are better methods, for example, on this page: Primary Test

Answer 3

As stated in the comments on sulfur, the implementation of the Eratosthenes sieve would be a good choice.