How does one implement IsPrime() function [duplicate]

This question already has answers here: 开发者_开发问答 Closed 12 years ago.

Possible Duplicates:

Program to find prime numbers in C#

prime numbers c#

Most elegant way to generate prime numbers

Hi Guys.

How does one check if a number is prime or not?

---

That's one I use to write any time i need to do this check:

inline bool isPrime(const int a)
{
    if(a == 1) return false;
    if(a == 2 || a == 3) return true;
    if(!(a & 1)) return false;
    if(!((a + 1)%6 || (a-1)%6)) return false;
    int q = sqrt((long double)a) + 1;
    for(int v = 3; v < q; v += 2)
        if(a % v == 0)
            return false;
    return true;
}

It works really well because of some useful prunings.

---

Don't know if there's a standard function for it, but you could always built a method using the Sieve of Eratosthenes (link: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes). Pretty easy to implement.

---

There are a couple of c# versions here: LTD Puzzle 4: Finding Prime Numbers There are also f#, c, JavaScript. PHP etc etc versions

---

If it is divisible by 1 or itself, it is prime. You can shorten the number of tests by realizing that all primes except 2 are odd, or it would be divisible by 2. Also, all prime numbers above 5 can be represented as 6n+1 or 6n-1, but not all numbers generated this way are primes. Additionally, the largest possible divisor of the number will be its square root. These facts are enough to make the test much faster than if you just tested all numbers till the number you want to check.