Prime Number Formula

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;
 }

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:

public bool CalcIsPrime(int number) {

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

    if (number % 2 == 0) return false; // Even number     

    for (int i = 2; i < number; i++) { // Advance from two to include correct calculation for '4'
       if (number % i == 0) return false;
    }

    return true;

}

For better algorithms check here: Primality Test

If you want to check your code, do inlcude a test, here's a test case written in xunit.

        [Theory]
        [MemberData(nameof(PrimeNumberTestData))]
        public void CalcIsPrimeTest(int number, bool expected) {
            Assert.Equal(expected, CalcIsPrime(number));
        }

        public static IEnumerable<object[]> PrimeNumberTestData() {
            yield return new object[] { 0, false };
            yield return new object[] { 1, false };
            yield return new object[] { 2, true };
            yield return new object[] { 3, true };
            yield return new object[] { 4, false };
            yield return new object[] { 5, true };
            yield return new object[] { 6, false };
            yield return new object[] { 7, true };
            yield return new object[] { 8, false };
            yield return new object[] { 9, false };
            yield return new object[] { 10, false };
            yield return new object[] { 11, true };
            yield return new object[] { 23, true };
            yield return new object[] { 31, true };
            yield return new object[] { 571, true };
            yield return new object[] { 853, true };
            yield return new object[] { 854, false };
            yield return new object[] { 997, true };
            yield return new object[] { 999, false };
        }

It had to be done...

public static bool IsPrime(this int number)
{
    return (Enumerable.Range(1,number).Where(x => number % x == 0).Count() == 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.

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.

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;
    }

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.

    static List<long> PrimeNumbers = new List<long>();

    static void Main(string[] args)
    {
        PrimeNumbers.Add(2);
        PrimeNumbers.Add(3);
        PrimeNumbers.Add(5);
        PrimeNumbers.Add(7);
        for (long i = 11; i < 10000000; i += 2)
        {
            if (i % 5 != 0)
                if (IsPrime(i))
                    PrimeNumbers.Add(i);
        }
    }

    static bool IsPrime(long number)
    {
        foreach (long i in PrimeNumbers)
        {
            if (i <= Math.Sqrt(number))
            {
                if (number % i == 0)
                    return false;
            }
            else
                break;
        }
        return true;
    }

this is a simple one

only odd numbers are prime....so

static bool IsPrime(int number)
{
int i;
if(number==2)
    return true;                    //if number is 2 then it will return prime
for(i=3,i<number/2;i=i+2)           //i<number/2 since a number cannot be 
  {                                     //divided by more then its half
    if(number%i==0)                 //if number is divisible by i, then its not a prime
          return false;
  }
return true;                        //the code will only reach here if control
}                                       //is not returned false in the for loop

This is a simple code for find prime number depend on your input.

  static void Main(string[] args)
    {
        String input = Console.ReadLine();
        long num = Convert.ToInt32(input);
        long a, b, c;
        c = 2;
        for(long i=3; i<=num; i++){
            b = 0;
            for (long j = 2; j < i ; j++) {
                a = i % j;
                if (a != 0) {
                    b = b+1;
                }
                else {
                    break;
                }
            }

            if(b == i-2){
                Console.WriteLine("{0}",i);
            }
        }
        Console.ReadLine();
    }

ExchangeCore Forums have a good bit of code that will pretty much let you generate any ulong number for primes. But basically here's the gist:

int primesToFind = 1000;
int[] primes = new int[primesToFind];
int primesFound = 1;
primes[0] = 2;
for(int i = 3; i < int.MaxValue() && primesFound < primesToFind; i++)
{
   bool isPrime = true;
   double sqrt = Math.sqrt(i);
   for(int j = 0; j<primesFound && primes[j] <= sqrt; j++)
   {
      if(i%primes[j] == 0)
      {
         isPrime = false;
         break;
      }
   }
   if(isPrime)
      primes[primesFound++] = i;
}

Once this code has finished running your primes will all be found in the primes array variable.

https://www.khanacademy.org/computing/computer-science/cryptography/comp-number-theory/a/trial-division

    public static bool isPrime(int number)
    {
        for (int k = 2; k <= Math.Ceiling(Math.Sqrt(number)); k++)
        {
            if (number > k && number % k == 0)
                break;
            if (k >= Math.Ceiling(Math.Sqrt(number)) || number == k)
            {
                return true;
            }
        }
        return false;
    }

Prime Numbers from 0 - 1 Million in less than two tenths of a second

Just finished it. Last test was 0.017 seconds.

Regular HP Laptop. 2.1 GHz

It takes longer when it gets larger. For primes 1 - 1 billion , my last test was 28.6897 seconds. It might be faster in your program because I was casting class objects to get parameter values in mine.

Method Info

• Uses the Sieve of Eratosthenes
• Accepts floor and ceiling as arguments
• Uses arrays instead of lists for fast performance
• Size of array is initialized according to Rosser-Schoenfeld upper bound
• Skips multiples of 2, 5, and 7 when assigning values
• Max range is between 0 and 2,147,483,646   (1 min 44.499 s)
• Heavily commented

Using

using System;
using System.Diagnostics;
using System.Collections;

Method

private static int[] GetPrimeArray(int floor, int ceiling)
{
    // Validate arguments.
    if (floor > int.MaxValue - 1)
        throw new ArgumentException("Floor is too high. Max: 2,147,483,646");
    else if (ceiling > int.MaxValue - 1)
        throw new ArgumentException("Ceiling is too high. Max: 2,147,483,646");
    else if (floor < 0)
        throw new ArgumentException("Floor must be a positive integer.");
    else if (ceiling < 0)
        throw new ArgumentException("Ceiling must be a positve integer.");
    else if (ceiling < floor)
        throw new ArgumentException("Ceiling cannot be less than floor.");

    // This region is only useful when testing performance.
    #region Performance

    Stopwatch sw = new Stopwatch();
    sw.Start();

    #endregion

    // Variables:
    int stoppingPoint = (int)Math.Sqrt(ceiling);
    double rosserBound = (1.25506 * (ceiling + 1)) / Math.Log(ceiling + 1, Math.E);
    int[] primeArray = new int[(int)rosserBound];
    int primeIndex = 0;
    int bitIndex = 4;
    int innerIndex = 3;

    // Handle single digit prime ranges.
    if (ceiling < 11)
    {
        if (floor <= 2 && ceiling >= 2) // Range includes 2.
            primeArray[primeIndex++] = 2;

        if (floor <= 3 && ceiling >= 3) // Range includes 3.
            primeArray[primeIndex++] = 3;

        if (floor <= 5 && ceiling >= 5) // Range includes 5.
            primeArray[primeIndex++] = 5;

        return primeArray;
    }

    // Begin Sieve of Eratosthenes. All values initialized as true.
    BitArray primeBits = new BitArray(ceiling + 1, true); 
    primeBits.Set(0, false); // Zero is not prime.
    primeBits.Set(1, false); // One is not prime.

    checked // Check overflow.
    {
        try
        {
            // Set even numbers, excluding 2, to false.
            for (bitIndex = 4; bitIndex < ceiling; bitIndex += 2)
                primeBits[bitIndex] = false;
        }
        catch { } // Break for() if overflow occurs.
    }

    // Iterate by steps of two in order to skip even values.
    for (bitIndex = 3; bitIndex <= stoppingPoint; bitIndex += 2)
    {
        if (primeBits[bitIndex] == true) // Is prime.
        {
            // First position to unset is always the squared value.
            innerIndex = bitIndex * bitIndex;
            primeBits[innerIndex] = false;

            checked // Check overflow.
            {
                try
                {
                    // Set multiples of i, which are odd, to false.
                    innerIndex += bitIndex + bitIndex;
                    while (innerIndex <= ceiling)
                    {
                        primeBits[innerIndex] = false;
                        innerIndex += bitIndex + bitIndex;
                    }
                }
                catch { continue; } // Break while() if overflow occurs.
            }
        }
    }

    // Set initial array values.
    if (floor <= 2)
    {
        // Range includes 2 - 5.
        primeArray[primeIndex++] = 2;
        primeArray[primeIndex++] = 3;
        primeArray[primeIndex++] = 5;
    }

    else if (floor <= 3)
    {
        // Range includes 3 - 5.
        primeArray[primeIndex++] = 3;
        primeArray[primeIndex++] = 5;
    }
    else if (floor <= 5)
    {
        // Range includes 5.
        primeArray[primeIndex++] = 5;
    }

    // Increment values that skip multiples of 2, 3, and 5.
    int[] increment = { 6, 4, 2, 4, 2, 4, 6, 2 };
    int indexModulus = -1;
    int moduloSkipAmount = (int)Math.Floor((double)(floor / 30));

    // Set bit index to increment range which includes the floor.
    bitIndex = moduloSkipAmount * 30 + 1;

    // Increase bit and increment indicies until the floor is reached.
    for (int i = 0; i < increment.Length; i++)
    {
        if (bitIndex >= floor)
            break; // Floor reached.

        // Increment, skipping multiples of 2, 3, and 5.
        bitIndex += increment[++indexModulus];
    }

    // Initialize values of return array.
    while (bitIndex <= ceiling)
    {
        // Add bit index to prime array, if true.
        if (primeBits[bitIndex])
            primeArray[primeIndex++] = bitIndex;

        checked // Check overflow.
        {
            try
            {
                // Increment. Skip multiples of 2, 3, and 5.
                indexModulus = ++indexModulus % 8;
                bitIndex += increment[indexModulus];
            }
            catch { break; } // Break if overflow occurs.
        }
    }

    // Resize array. Rosser-Schoenfeld upper bound of π(x) is not an equality.
    Array.Resize(ref primeArray, primeIndex);

    // This region is only useful when testing performance.
    #region Performance

    sw.Stop();

    if (primeArray.Length == 0)
        Console.WriteLine("There are no prime numbers between {0} and {1}",
            floor, ceiling);
    else
    {
        Console.WriteLine(Environment.NewLine);
        for (int i = 0; i < primeArray.Length; i++)
            Console.WriteLine("{0,10}:\t\t{1,15:#,###,###,###}", i + 1, primeArray[i]);
    }

    Console.WriteLine();
    Console.WriteLine("Calculation time:\t{0}", sw.Elapsed.ToString());

    #endregion

    return primeArray;
}

Comments are welcome! Especially improvements.

Here we must have to consider the square root factor. A prime number can be verified if it is not divisible by any number less than the value of square root of any near number.

static bool isPrime(long number) 
{
    if (number == 1) return false;
    if (number == 2) return true;
    if (number % 2 == 0) return false; //Even number     
    long nn= (long) Math.Abs(Math.Sqrt(number));
    for (long i = 3; i < nn; i += 2)  {
       if (number % i == 0) return false;
    }
    return true;
}