Check if number is prime number

Question

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  lt   num1   2  a                  if  num1   a    0                        Console WriteLine num1     is not prime number                return                       Console WriteLine num1     is a prime number        Console ReadLine

User · Answer

I think this is the easiest way to do it   static bool IsPrime int number       for  int i   2  i  lt   number 2  i           if  number   i    0             return false      return true

User · Answer

Here s a nice way of doing that       static bool IsPrime int n                if  n  gt  1                        return Enumerable Range 1  n  Where x   gt  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

User · Answer

You can also try this   bool isPrime int number                return  Enumerable Range 1  number  Count x   gt  number   x    0     2

User · Answer

Based on  Micheal s answer  but checks for negative numbers and computes the square incrementally      public static bool IsPrime  int candidate             if   candidate   2  lt   0                 return candidate    2                    int power2   9          for   int divisor   3  power2  lt   candidate  divisor    2                 if   candidate   divisor    0                   return false              power2    divisor   4   4                    return true

User · Answer

Here is a version without the  clutter  of other answers and simply does the trick     static void Main string   args         Console WriteLine  Enter your number          int num   Convert ToInt32 Console ReadLine         bool isPrime   true      for  int i   2  i  lt  num 2  i                  if  num   i    0                        isPrime   false              break                      if  isPrime          Console WriteLine  It is Prime        else         Console WriteLine  It is not Prime        Console ReadLine

User · Answer

A prime number is odd except 2 1 or 0 is neither prime nor composite  Approach  Add a counter to check how many times the input number is divisible by i  and has 0  zero  remainder  If counter is   2  then input is prime  else not prime If counter is  gt  2  quot break quot  to avoid unnecessary processes  if you want to count the factors of your input number remove  quot     counter  gt  2  quot  on the first if statement  Add this line of code at the 2nd if statement inside the for loop if you want to see how many numbers with remainder 0  or factors are present     Console WriteLine    quot   inputNumber     i      inputNumber   i   remainder   inputNumber   i   quot        Add the line of code in number 4  at the end of the for loop  to see all the all the numbers divided by your input number  in case you want to see the remainder output and the quotient   Console Write   quot Enter a Positive Number   quot     int inputNumber   Convert ToInt32  Console ReadLine      int counter   0       for   int i   1  i  lt   inputNumber  i               if   inputNumber    0    inputNumber    1    counter  gt  2     break            if   inputNumber   i    0     counter                 if   counter    2             Console WriteLine    quot  inputNumber  is a prime number  quot           else if   inputNumber    1    inputNumber    0             Console WriteLine    quot  inputNumber  is neither prime nor composite  quot           else           Console WriteLine    quot  inputNumber  is not a prime number   It is a composite number  quot            My reference  https   www tutorialspoint com Chash-Program-to-check-if-a-number-is-prime-or-not

User · Answer

Check a number is prime or not     param n the number     return   code true  if   code n  is prime     public static boolean isPrime int n        if  n    2            return true            if  n  lt  2    n   2    0            return false            for  int i   3  i  lt   Math sqrt n   i    2            if  n   i    0                return false                      return true

User · Answer

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 lt int gt  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 lt int gt  KnownRootPrimesList          public int HighestKnownPrime   3           public PrimeChecker int Max 1000000               KnownRootPrimesList   new List lt int gt                 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  gt  HighestKnownPrime                                for int i   HighestKnownPrime   1  i  lt   srt  i                                          if  i  gt  HighestKnownPrime                                                if isPrimeCalculation i                                                             KnownRootPrimesList Add i                                   HighestKnownPrime   i                                                                                              bool isValuePrime   isPrimeCalculation value               return isValuePrime                      private bool isPrimeCalculation int value                        if  value  lt  HighestKnownPrime                                if  KnownRootPrimesList BinarySearch value   gt  -1                                        return  true                                     else                                       return  false                                               int srt   Convert ToInt32 Math Ceiling Math Sqrt Convert ToDouble value                  bool isPrime   true              List lt int gt  CheckList   KnownRootPrimesList ToList                if  HighestKnownPrime   1  lt  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 lt int gt  CheckList   Enumerable Range 2  srt  ToList                foreach  int i in CheckList                                isPrime     value   i     0                   if   isPrime                                        break                                              return  isPrime

User · Answer

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  quot Please Enter a number   quot            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  amp  amp  count  lt   sqrtOfNumber                        if   number   count    0                            Console WriteLine   quot  number  isn t prime and it divisible by                                        number  count  quot        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  amp  amp  number  gt  1                                 Console WriteLine   quot  number  is a prime number quot                      else if  prime    true             if input is 1 or less than 1 then this code will generate                       Console WriteLine   quot  number  isn t a prime quot

User · Answer

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  lt   limit    i           if  number   i    0               return false      return true

User · Answer

Only one row code       private static bool primeNumberTest int i                return i  gt  3      Enumerable Range 2   i   2    1  Where x   gt   i   x    0    Count    gt  0   false   true     i    2    i    3   true   false

User · Answer

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  gt  0                int bitLength   value ToByteArray   Length   8          BigInteger root   BigInteger One  lt  lt   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  gt   lowerBound  amp  amp  n  lt  upperBound      static bool IsPrime BigInteger value        Console WriteLine  Checking if  0  is a prime number    value       if  value  lt  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      gt                                for  BigInteger i   11  i  lt   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      gt                                for  BigInteger i   3  i  lt   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      gt                                for  BigInteger i   7  i  lt   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      gt                                for  BigInteger i   9  i  lt   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      gt                                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  lt  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  lt  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  lt  2    a  gt   source - 2          BigInteger x   BigInteger ModPow a  d  source         if x    1    x    source - 1          continue         for int r   1  r  lt  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

User · Answer

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  lt   inp  i                                  for  int j   2  j  lt  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

User · Answer

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  lt   n                                if   n   k     0                      return false                  else k                              return true

User · Answer

This is the simplest way to find prime number is  for i 2  i lt 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

User · Answer

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  lt   n                                if   n   k     0                      return false                  else return isPrime n  k   1                             else                 return true

User · Answer

Shortest technique to find Prime Number using conventional way       public string IsPrimeNumber int Number                int i   2  j   Number   2          for    i  lt   j  amp  amp  Number   2    0  i             return  i - 1     j    Prime Number     Not Prime Number

User · Answer

var number   Console WriteLine  quot Accept number  quot    number   Convert ToInt32 Console ReadLine      if  IsPrime number         Console WriteLine  quot It is prime quot      else       Console WriteLine  quot It is not prime quot              public static bool IsPrime int number        if  number  lt   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  lt   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    then one of the factors a or b is necessarily at most square root of n

User · Answer

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  lt   boundary                        if  number    i   1     0    number    i   5     0                  return false               i    6                     return true

User · Answer

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   gt  n   x    0

User · Answer

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 gt 2                        IsPrime n  prime                           Method     public static void IsPrime BigInteger n  bool prime                bool local   false          for  int i 2  i lt   BigInteger Math Sqrt  double n   i                          if  n   i    0                                local   true                  break                                  if  local                                Console WriteLine prime                         else                       prime   true              Console WriteLine prime

User · Answer

bool flag   false                for  int n   1 n  lt  101 n                                  if  n    1    n    2                                        Console WriteLine  prime                                       else                                       for  int i   2  i  lt  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

User · Answer

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  lt   k                        if  n   j    0                  return false              j   j   2                    return true

User · Answer

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  lt  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

User · Answer

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  lt  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  lt  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  amp  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   lt   candidate  i    2                if   candidate   i     0                    return false                      return candidate    1

[c#] Check if number is prime number

Examples related to c#

Examples related to primes

Examples related to primality-test