Prime Number Formula

Question

I am trying to write a prime number function in C# and I am wondering if the follow code will work. It "appears" to work with the first 50 numbers or so. I just want to make sure it will work no matter how big the number is:

static bool IsPrime(int number)
{
    if ((number == 2) || (number == 3) || (number == 5) || (number == 7) || (number == 9))
            return true;

    if ((number % 2 != 0) && (number % 3 != 0) && (number % 5 != 0) &&
        (number % 7 != 0) && (number % 9 != 0) && (number % 4 != 0) &&
        (number % 6 != 0))
        return true;

        return false;
 }

Answer 1

No it won't work! Try 121 = 11 * 11 for example which obviously isn't a prime.

For any number given to your function, that is a product of the prime numbers X1, X2, ..., Xn(where n >= 2) with all of them being greater or equal to 11, your function will return true. (And also, as already said, 9 isn't a prime).

From wikipedia you can see that:

In mathematics, a prime number (or a prime) is a natural number that has exactly two distinct natural number divisors: 1 and itself.

so a very simple and naive algorithm on checking whether a number is prime could be:

boolean isPrime(int number) {

    if (number == 1) return false;
    if (number == 2) return true;

    for (int i = 2; i < number; ++i)  {
       if (number % i = 0) return false;
    }

    return true;

}

For better algorithms check here: Primality Test

Answer 2

This approach definitely won't work, unless your if statement explicitly enumerates all the prime numbers between 0 and sqrt(INT_MAX) (or the C# equivalent).

To properly check for primality, you basically need to attempt to divide your number by every prime number less than its square root. The Sieve of Eratosthenes algorithm is your best bet.

Answer 3

You are apparently writing from a contrafactual dimension where 9 is a prime number, so I guess that our answers might not work for you. Two things though:

1. Prime number generating functions are a non-trivial but exiting matter, the Wikipedia page is a good starter (http://en.wikipedia.org/wiki/Formula_for_primes)

2. from (number%2!=0) it follows (number%4!=0). If you can't divide by 10, then you can't divide by 100 either.

Answer 4

Your function returns true for even numbers.

I highly doubt this will work for the general case. Primality testing is very involved.

Answer 5

It had to be done...

public static bool IsPrime(this int number)
{
    return (Enumerable.Range(1,number).Where(x => number % x == 0).Count() == 2);
}

Answer 6

Primality testing is the way to go, but in case you want a quick and dirty hack, here's something.

If it's not working fast enough, you can build a class around it and store the PrimeNumbers collection from call to call, rather than repopulating it for each call.

    public bool IsPrime(int val)
    {
        Collection<int> PrimeNumbers = new Collection<int>();
        int CheckNumber = 5;
        bool divisible = true;
        PrimeNumbers.Add(2);
        PrimeNumbers.Add(3);

        // Populating the Prime Number Collection
        while (CheckNumber < val)
        {
            foreach (int i in PrimeNumbers)
            {
                if (CheckNumber % i == 0)
                {
                    divisible = false;
                    break;
                }
                if (i * i > CheckNumber) { break; }
            }
            if (divisible == true) { PrimeNumbers.Add(CheckNumber); }
            else { divisible = true; }
            CheckNumber += 2;
        }
        foreach (int i in PrimeNumbers)
        {
            if (CheckNumber % i == 0)
            {
                divisible = false;
                break;
            }
            if (i * i > CheckNumber) { break; }
        }
        if (divisible == true) { PrimeNumbers.Add(CheckNumber); }
        else { divisible = true; }

        // Use the Prime Number Collection to determine if val is prime
        foreach (int i in PrimeNumbers)
        {
            if (val % i == 0) { return false; }
            if (i * i > val) { return true; }
        }
        // Shouldn't ever get here, but needed to build properly.
        return true;
    }

Answer 7

There are some basic rules you can follow to check if a number is prime

1. Even numbers are out. If x % 2 = 0, then it is not prime
2. All non-prime numbers have prime factors. Therefore, you only need test a number against primes to see if it factors
3. The highest possible factor any number has is it's square root. You only need to check if values <= sqrt(number_to_check) are even divisible.

Using that set of logic, the following formula calculates 1,000,000 Primes Generated in: 134.4164416 secs in C# in a single thread.

    public IEnumerable<long> GetPrimes(int numberPrimes)
    {
      List<long> primes = new List<long> { 1, 2, 3 };
      long startTest = 3;

      while (primes.Count() < numberPrimes)
      {
        startTest += 2;
        bool prime = true;
        for (int pos = 2; pos < primes.Count() && primes[pos] <= Math.Sqrt(startTest); pos++)
        {
          if (startTest % primes[pos] == 0)
          {
            prime = false;
          }
        }
        if (prime)
          primes.Add(startTest);
      }
      return primes;
    }

Bear in mind, there is lots of room for optimization in the algorithm. For example, the algorithm could be parallelized. If you have a prime number (let's say 51), you can test all the numbers up to it's square (2601) for primeness in seperate threads as all it's possible prime factors are stored in the list.