Check if number is prime number

I would just like to ask if this is a correct way of checking if number is prime or not? because I read that 0 and 1 are NOT a prime number.

int num1;

Console.WriteLine("Accept number:");
num1 = Convert.ToInt32(Console.ReadLine());
if (num1 == 0 || num1 == 1)
{
    Console.WriteLine(num1 + " is not prime number");
    Console.ReadLine();
}
else
{
    for (int a = 2; a <= num1 / 2; a++)
    {
        if (num1 % a == 0)
        {
            Console.WriteLine(num1 + " is not prime number");
            return;
        }

    }
    Console.WriteLine(num1 + " is a prime number");
    Console.ReadLine();
}

Answers


var number;

Console.WriteLine("Accept number:");
number = Convert.ToInt32(Console.ReadLine());
if(IsPrime(number))
{
  Console.WriteLine("It is prime");
}
else
{
  Console.WriteLine("It is not prime");
}       

public static bool IsPrime(int number)
{
    if (number <= 1) return false;
    if (number == 2) return true;
    if (number % 2 == 0) return false;

    var boundary = (int)Math.Floor(Math.Sqrt(number));

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

    return true;        
}

I changed number / 2 to Math.Sqrt(number) because from in wikipedia, they said:

This routine consists of dividing n by each integer m that is greater than 1 and less than or equal to the square root of n. If the result of any of these divisions is an integer, then n is not a prime, otherwise it is a prime. Indeed, if n = a*b is composite (with a and b ≠ 1) then one of the factors a or b is necessarily at most square root of n


Using Soner's routine, but with a slight variation: we will run until i equals Math.Ceiling(Math.Sqrt(number)) that is the trick for the naive solution:

boolean isPrime(int number)
{

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

    var limit = Math.Ceiling(Math.Sqrt(number)); //hoisting the loop limit

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

    return true;

}

Here's a nice way of doing that.

    static bool IsPrime(int n)
    {
        if (n > 1)
        {
            return Enumerable.Range(1, n).Where(x => n%x == 0)
                             .SequenceEqual(new[] {1, n});
        }

        return false;
    }

And a quick way of writing your program will be:

        for (;;)
        {
            Console.Write("Accept number: ");
            int n = int.Parse(Console.ReadLine());
            if (IsPrime(n))
            {
                Console.WriteLine("{0} is a prime number",n);
            }
            else
            {
                Console.WriteLine("{0} is not a prime number",n);
            }
        }

Here's a good example. I'm dropping the code in here just in case the site goes down one day.

using System;

class Program
{
    static void Main()
    {
    //
    // Write prime numbers between 0 and 100.
    //
    Console.WriteLine("--- Primes between 0 and 100 ---");
    for (int i = 0; i < 100; i++)
    {
        bool prime = PrimeTool.IsPrime(i);
        if (prime)
        {
        Console.Write("Prime: ");
        Console.WriteLine(i);
        }
    }
    //
    // Write prime numbers between 10000 and 10100
    //
    Console.WriteLine("--- Primes between 10000 and 10100 ---");
    for (int i = 10000; i < 10100; i++)
    {
        if (PrimeTool.IsPrime(i))
        {
        Console.Write("Prime: ");
        Console.WriteLine(i);
        }
    }
    }
}

Here is the class that contains the IsPrime method:

using System;

public static class PrimeTool
{
    public static bool IsPrime(int candidate)
    {
    // Test whether the parameter is a prime number.
    if ((candidate & 1) == 0)
    {
        if (candidate == 2)
        {
        return true;
        }
        else
        {
        return false;
        }
    }
    // Note:
    // ... This version was changed to test the square.
    // ... Original version tested against the square root.
    // ... Also we exclude 1 at the end.
    for (int i = 3; (i * i) <= candidate; i += 2)
    {
        if ((candidate % i) == 0)
        {
        return false;
        }
    }
    return candidate != 1;
    }
}

I've implemented a different method to check for primes because:

  • Most of these solutions keep iterating through the same multiple unnecessarily (for example, they check 5, 10, and then 15, something that a single % by 5 will test for).
  • A % by 2 will handle all even numbers (all integers ending in 0, 2, 4, 6, or 8).
  • A % by 5 will handle all multiples of 5 (all integers ending in 5).
  • What's left is to test for even divisions by integers ending in 1, 3, 7, or 9. But the beauty is that we can increment by 10 at a time, instead of going up by 2, and I will demonstrate a solution that is threaded out.
  • The other algorithms are not threaded out, so they don't take advantage of your cores as much as I would have hoped.
  • I also needed support for really large primes, so I needed to use the BigInteger data-type instead of int, long, etc.

Here is my implementation:

public static BigInteger IntegerSquareRoot(BigInteger value)
{
    if (value > 0)
    {
        int bitLength = value.ToByteArray().Length * 8;
        BigInteger root = BigInteger.One << (bitLength / 2);
        while (!IsSquareRoot(value, root))
        {
            root += value / root;
            root /= 2;
        }
        return root;
    }
    else return 0;
}

private static Boolean IsSquareRoot(BigInteger n, BigInteger root)
{
    BigInteger lowerBound = root * root;
    BigInteger upperBound = (root + 1) * (root + 1);
    return (n >= lowerBound && n < upperBound);
}

static bool IsPrime(BigInteger value)
{
    Console.WriteLine("Checking if {0} is a prime number.", value);
    if (value < 3)
    {
        if (value == 2)
        {
            Console.WriteLine("{0} is a prime number.", value);
            return true;
        }
        else
        {
            Console.WriteLine("{0} is not a prime number because it is below 2.", value);
            return false;
        }
    }
    else
    {
        if (value % 2 == 0)
        {
            Console.WriteLine("{0} is not a prime number because it is divisible by 2.", value);
            return false;
        }
        else if (value == 5)
        {
            Console.WriteLine("{0} is a prime number.", value);
            return true;
        }
        else if (value % 5 == 0)
        {
            Console.WriteLine("{0} is not a prime number because it is divisible by 5.", value);
            return false;
        }
        else
        {
            // The only way this number is a prime number at this point is if it is divisible by numbers ending with 1, 3, 7, and 9.
            AutoResetEvent success = new AutoResetEvent(false);
            AutoResetEvent failure = new AutoResetEvent(false);
            AutoResetEvent onesSucceeded = new AutoResetEvent(false);
            AutoResetEvent threesSucceeded = new AutoResetEvent(false);
            AutoResetEvent sevensSucceeded = new AutoResetEvent(false);
            AutoResetEvent ninesSucceeded = new AutoResetEvent(false);
            BigInteger squareRootedValue = IntegerSquareRoot(value);
            Thread ones = new Thread(() =>
            {
                for (BigInteger i = 11; i <= squareRootedValue; i += 10)
                {
                    if (value % i == 0)
                    {
                        Console.WriteLine("{0} is not a prime number because it is divisible by {1}.", value, i);
                        failure.Set();
                    }
                }
                onesSucceeded.Set();
            });
            ones.Start();
            Thread threes = new Thread(() =>
            {
                for (BigInteger i = 3; i <= squareRootedValue; i += 10)
                {
                    if (value % i == 0)
                    {
                        Console.WriteLine("{0} is not a prime number because it is divisible by {1}.", value, i);
                        failure.Set();
                    }
                }
                threesSucceeded.Set();
            });
            threes.Start();
            Thread sevens = new Thread(() =>
            {
                for (BigInteger i = 7; i <= squareRootedValue; i += 10)
                {
                    if (value % i == 0)
                    {
                        Console.WriteLine("{0} is not a prime number because it is divisible by {1}.", value, i);
                        failure.Set();
                    }
                }
                sevensSucceeded.Set();
            });
            sevens.Start();
            Thread nines = new Thread(() =>
            {
                for (BigInteger i = 9; i <= squareRootedValue; i += 10)
                {
                    if (value % i == 0)
                    {
                        Console.WriteLine("{0} is not a prime number because it is divisible by {1}.", value, i);
                        failure.Set();
                    }
                }
                ninesSucceeded.Set();
            });
            nines.Start();
            Thread successWaiter = new Thread(() =>
            {
                AutoResetEvent.WaitAll(new WaitHandle[] { onesSucceeded, threesSucceeded, sevensSucceeded, ninesSucceeded });
                success.Set();
            });
            successWaiter.Start();
            int result = AutoResetEvent.WaitAny(new WaitHandle[] { success, failure });
            try
            {
                successWaiter.Abort();
            }
            catch { }
            try
            {
                ones.Abort();
            }
            catch { }
            try
            {
                threes.Abort();
            }
            catch { }
            try
            {
                sevens.Abort();
            }
            catch { }
            try
            {
                nines.Abort();
            }
            catch { }
            if (result == 1)
            {
                return false;
            }
            else
            {
                Console.WriteLine("{0} is a prime number.", value);
                return true;
            }
        }
    }
}

Update: If you want to implement a solution with trial division more rapidly, you might consider having a cache of prime numbers. A number is only prime if it is not divisible by other prime numbers that are up to the value of its square root. Other than that, you might consider using the probabilistic version of the Miller-Rabin primality test to check for a number's primality if you are dealing with large enough values (taken from Rosetta Code in case the site ever goes down):

// Miller-Rabin primality test as an extension method on the BigInteger type.
// Based on the Ruby implementation on this page.
public static class BigIntegerExtensions
{
  public static bool IsProbablePrime(this BigInteger source, int certainty)
  {
    if(source == 2 || source == 3)
      return true;
    if(source < 2 || source % 2 == 0)
      return false;

    BigInteger d = source - 1;
    int s = 0;

    while(d % 2 == 0)
    {
      d /= 2;
      s += 1;
    }

    // There is no built-in method for generating random BigInteger values.
    // Instead, random BigIntegers are constructed from randomly generated
    // byte arrays of the same length as the source.
    RandomNumberGenerator rng = RandomNumberGenerator.Create();
    byte[] bytes = new byte[source.ToByteArray().LongLength];
    BigInteger a;

    for(int i = 0; i < certainty; i++)
    {
      do
      {
        // This may raise an exception in Mono 2.10.8 and earlier.
        // http://bugzilla.xamarin.com/show_bug.cgi?id=2761
        rng.GetBytes(bytes);
        a = new BigInteger(bytes);
      }
      while(a < 2 || a >= source - 2);

      BigInteger x = BigInteger.ModPow(a, d, source);
      if(x == 1 || x == source - 1)
        continue;

      for(int r = 1; r < s; r++)
      {
        x = BigInteger.ModPow(x, 2, source);
        if(x == 1)
          return false;
        if(x == source - 1)
          break;
      }

      if(x != source - 1)
        return false;
    }

    return true;
  }
}

Based on @Micheal's answer, but checks for negative numbers and computes the square incrementally

    public static bool IsPrime( int candidate ) {
        if ( candidate % 2 <= 0 ) {
            return candidate == 2;
        }
        int power2 = 9;
        for ( int divisor = 3; power2 <= candidate; divisor += 2 ) {
            if ( candidate % divisor == 0 )
                return false;
            power2 += divisor * 4 + 4;
        }
        return true;
    }

Find this example in one book, and think it's quite elegant solution.

 static void Main(string[] args)
    {
        Console.Write("Enter a number: ");
        int theNum = int.Parse(Console.ReadLine());

        if (theNum < 3)  // special case check, less than 3
        {
            if (theNum == 2)
            {
                // The only positive number that is a prime
                Console.WriteLine("{0} is a prime!", theNum);
            }
            else
            {
                // All others, including 1 and all negative numbers, 
                // are not primes
                Console.WriteLine("{0} is not a prime", theNum);
            }
        }
        else
        {
            if (theNum % 2 == 0)
            {
                // Is the number even?  If yes it cannot be a prime
                Console.WriteLine("{0} is not a prime", theNum);
            }
            else
            {
                // If number is odd, it could be a prime
                int div;

                // This loop starts and 3 and does a modulo operation on all
                // numbers.  As soon as there is no remainder, the loop stops.
                // This can be true under only two circumstances:  The value of
                // div becomes equal to theNum, or theNum is divided evenly by 
                // another value.
                for (div = 3; theNum % div != 0; div += 2)
                    ;  // do nothing

                if (div == theNum)
                {
                    // if theNum and div are equal it must be a prime
                    Console.WriteLine("{0} is a prime!", theNum);
                }
                else
                {
                    // some other number divided evenly into theNum, and it is not
                    // itself, so it is not a prime
                    Console.WriteLine("{0} is not a prime", theNum);
                }
            }
        }

        Console.ReadLine();
    }

You can also find range of prime numbers till the given number by user.

CODE:

class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Input a number to find Prime numbers\n");
            int inp = Convert.ToInt32(Console.ReadLine());
            Console.WriteLine("\n Prime Numbers are:\n------------------------------");
            int count = 0;

            for (int i = 1; i <= inp; i++)
            {
                for (int j = 2; j < i; j++) // j=2 because if we divide any number with 1 the remaider will always 0, so skip this step to minimize time duration.
                {
                    if (i % j != 0)
                    {
                        count += 1;
                    }
                }
                if (count == (i - 2))
                    {
                        Console.Write(i + "\t"); 
                    }

                count = 0;
            }

            Console.ReadKey();

        }
    }


This version calculates a list of primes square roots and only checks if the list of prime numbers below the square root, and uses a binarysearch in the list to find known primes. I looped through to check the first 1,000,000 primes, and it took about 7 seconds.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication5
{
    class Program
    {
        static void Main(string[] args)
        {
            //test();
            testMax();
            Console.ReadLine();
        }

        static void testMax()
        {
            List<int> CheckPrimes = Enumerable.Range(2, 1000000).ToList();
            PrimeChecker pc = new PrimeChecker(1000000);
            foreach (int i in CheckPrimes)
            {
                if (pc.isPrime(i))
                {
                    Console.WriteLine(i);
                }
            }
        }
    }

    public class PrimeChecker{
        public List<int> KnownRootPrimesList;
        public int HighestKnownPrime = 3;

        public PrimeChecker(int Max=1000000){
            KnownRootPrimesList = new List<int>();
            KnownRootPrimesList.Add(2);
            KnownRootPrimesList.Add(3);
            isPrime(Max);
        }

        public bool isPrime(int value)
        {
            int srt = Convert.ToInt32(Math.Ceiling(Math.Sqrt(Convert.ToDouble(value))));
            if(srt > HighestKnownPrime)
            {
                for(int i = HighestKnownPrime + 1; i <= srt; i++)
                {
                    if (i > HighestKnownPrime)
                    {
                        if(isPrimeCalculation(i))
                        {
                                KnownRootPrimesList.Add(i);
                                HighestKnownPrime = i;
                        }
                    }
                }
            }
            bool isValuePrime = isPrimeCalculation(value);
            return(isValuePrime);
        }

        private bool isPrimeCalculation(int value)
        {
            if (value < HighestKnownPrime)
            {
                if (KnownRootPrimesList.BinarySearch(value) > -1)
                {
                    return (true);
                }
                else
                {
                    return (false);
                }
            }
            int srt = Convert.ToInt32(Math.Ceiling(Math.Sqrt(Convert.ToDouble(value))));
            bool isPrime = true;
            List<int> CheckList = KnownRootPrimesList.ToList();
            if (HighestKnownPrime + 1 < srt)
            {
                CheckList.AddRange(Enumerable.Range(HighestKnownPrime + 1, srt));
            }
            foreach(int i in CheckList)
            {
                isPrime = ((value % i) != 0);
                if(!isPrime)
                {
                    break;
                }
            }
            return (isPrime);
        }

        public bool isPrimeStandard(int value)
        {
            int srt = Convert.ToInt32(Math.Ceiling(Math.Sqrt(Convert.ToDouble(value))));
            bool isPrime = true;
            List<int> CheckList = Enumerable.Range(2, srt).ToList();
            foreach (int i in CheckList)
            {
                isPrime = ((value % i) != 0);
                if (!isPrime)
                {
                    break;
                }
            }
            return (isPrime);
        }
    }
}

This is basically an implementation of a brilliant suggestion made by Eric Lippert somewhere above.

    public static bool isPrime(int number)
    {
        if (number == 1) return false;
        if (number == 2 || number == 3 || number == 5) return true;
        if (number % 2 == 0 || number % 3 == 0 || number % 5 == 0) return false;

        var boundary = (int)Math.Floor(Math.Sqrt(number));

        // You can do less work by observing that at this point, all primes 
        // other than 2 and 3 leave a remainder of either 1 or 5 when divided by 6. 
        // The other possible remainders have been taken care of.
        int i = 6; // start from 6, since others below have been handled.
        while (i <= boundary)
        {
            if (number % (i + 1) == 0 || number % (i + 5) == 0)
                return false;

            i += 6;
        }

        return true;
    }

I think this is a simple way for beginners:

using System;
using System.Numerics;
public class PrimeChecker
{
    public static void Main()
    {
    // Input
        Console.WriteLine("Enter number to check is it prime: ");
        BigInteger n = BigInteger.Parse(Console.ReadLine());
        bool prime = false;

    // Logic
        if ( n==0 || n==1)
        {
            Console.WriteLine(prime);
        }
        else if ( n==2 )
        {
            prime = true;
            Console.WriteLine(prime);
        }
        else if (n>2)
        {
            IsPrime(n, prime);
        }
    }

    // Method
    public static void IsPrime(BigInteger n, bool prime)
    {
        bool local = false;
        for (int i=2; i<=(BigInteger)Math.Sqrt((double)n); i++)
        {
            if (n % i == 0)
            {
                local = true;
                break;
            }
        }
        if (local)
            {
                Console.WriteLine(prime);
            }
        else
        {
            prime = true;
            Console.WriteLine(prime);
        }
    }
}

The algorithm in the function consists of testing whether n is a multiple of any integer between 2 and sqrt (n). If it's not, then True is returned which means the number (n) is a prime number, otherwise False is returned which means n divides a number that is between 2 and the floor integer part of sqrt(n).

private static bool isPrime(int n)
        {
            int k = 2;
            while (k * k <= n)
            {
                if ((n % k) == 0)
                    return false;
                else k++;
            }
            return true;
        }

The algorithm in the function consists of testing whether n is a multiple of any integer between 2 and sqrt (n). If it's not, then True is returned which means the number (n) is a prime number, otherwise False is returned which means n divides a number that is between 2 and the floor integer part of sqrt(n).

Recursive version

        // Always call it as isPrime(n,2)
        private static bool isPrime(int n, int k)
        {
            if (k * k <= n)
            {
                if ((n % k) == 0)
                    return false;
                else return isPrime(n, k + 1);
            }
            else
                return true;
        }

Prime numbers are numbers that are bigger than one and cannot be divided evenly by any other number except 1 and itself.

@This program will show you the given number is prime or not, and will show you for non prime number that it's divisible by (a number) which is rather than 1 or itself?@

        Console.Write("Please Enter a number: ");
        int number = int.Parse(Console.ReadLine());
        int count = 2; 
        // this is initial count number which is greater than 1

        bool prime = true;
        // used Boolean value to apply condition correctly

        int sqrtOfNumber = (int)Math.Sqrt(number); 
        // square root of input number this would help to simplify the looping.  

        while (prime && count <= sqrtOfNumber)
        {
            if ( number % count == 0)
            {
            Console.WriteLine($"{number} isn't prime and it divisible by 
                                      number {count}");  // this will generate a number isn't prime and it is divisible by a number which is rather than 1 or itself and this line will proves why it's not a prime number.
                prime = false;
            }

            count++;

        }
        if (prime && number > 1)

        {
            Console.WriteLine($"{number} is a prime number");
        }
        else if (prime == true)
        // if input is 1 or less than 1 then this code will generate
        {
            Console.WriteLine($"{number} isn't a prime");
        }

I'm trying to get some efficiency out of early exit when using Any()...

    public static bool IsPrime(long n)
    {
        if (n == 1) return false;
        if (n == 3) return true;

        //Even numbers are not primes
        if (n % 2 == 0) return false;

        return !Enumerable.Range(2, Convert.ToInt32(Math.Ceiling(Math.Sqrt(n))))
            .Any(x => n % x == 0);
    }

This is the simplest way to find prime number is

for(i=2; i<num; i++)
        {
            if(num%i == 0)
            {
                count++;
                break;
            }
        }
        if(count == 0)
        {
            Console.WriteLine("This is a Prime Number");
        }
        else
        {
            Console.WriteLine("This is not a Prime Number");
        }

Helpful Link: https://codescracker.com/java/program/java-program-check-prime.htm


   bool flag = false;


            for (int n = 1;n < 101;n++)
            {
                if (n == 1 || n == 2)
                {
                    Console.WriteLine("prime");
                }

                else
                {
                    for (int i = 2; i < n; i++)
                    {
                        if (n % i == 0)
                        {
                            flag = true;
                            break;
                        }
                    }
                }

                if (flag)
                {
                    Console.WriteLine(n+" not prime");
                }
                else
                {
                    Console.WriteLine(n + " prime");
                }
                 flag = false;
            }

            Console.ReadLine();

Only one row code:

    private static bool primeNumberTest(int i)
    {
        return i > 3 ? ( (Enumerable.Range(2, (i / 2) + 1).Where(x => (i % x == 0))).Count() > 0 ? false : true ) : i == 2 || i == 3 ? true : false;
    }

Try this code.

bool isPrimeNubmer(int n)
{
    if (n == 2 || n == 3) //2, 3 are prime numbers
        return true;
    else if (n % 2 == 0) //even numbers are not prime numbers
        return false;
    else
    {
        int j = 3;
        int k = (n + 1) / 2 ;

        while (j <= k)
        {
            if (n % j == 0)
                return false;
            j = j + 2;
        }
        return true;
    }
}

You can also try this:

bool isPrime(int number)
    {
        return (Enumerable.Range(1, number).Count(x => number % x == 0) == 2);
    }

Need Your Help

Django tests - patch object in all tests

python django unit-testing django-testing python-mock

I need to create some kind of MockMixin for my tests. It should include mocks for everything that calls external sources.