C - determine if a number is prime

Question

I am trying to come up with a method that takes an integer and returns a boolean to say if the number is prime or not and I don t know much C  would anyone care to give me some pointers   Basically  I would do this in C  like this   static bool IsPrime int number        for  int i   2  i  lt  number  i                  if  number   i    0  amp  amp  i    number              return false            return true

User · Answer

Build a table of small primes  and check if they divide your input number  If the number survived to 1  try pseudo primality tests with increasing basis  See Miller-Rabin primality test for example  If your number survived to 2  you can conclude it is prime if it is below some well known bounds  Otherwise your answer will only be  probably prime   You will find some values for these bounds in the wiki page

User · Answer

OK  so forget about C   Suppose I give you a number and ask you to determine if it s prime   How do you do it   Write down the steps clearly  then worry about translating them into code   Once you have the algorithm determined  it will be much easier for you to figure out how to write a program  and for others to help you with it   edit  Here s the C  code you posted   static bool IsPrime int number        for  int i   2  i  lt  number  i              if  number   i    0  amp  amp  i    number  return false            return true      This is very nearly valid C as is  there s no bool type in C  and no true or false  so you need to modify it a little bit  edit  Kristopher Johnson correctly points out that C99 added the stdbool h header    Since some people don t have access to a C99 environment  but you should use one    let s make that very minor change   int IsPrime int number        int i      for  i 2  i lt number  i              if  number   i    0  amp  amp  i    number  return 0            return 1      This is a perfectly valid C program that does what you want   We can improve it a little bit without too much effort   First  note that i is always less than number  so the check that i    number always succeeds  we can get rid of it   Also  you don t actually need to try divisors all the way up to number - 1  you can stop checking when you reach sqrt number    Since sqrt is a floating-point operation and that brings a whole pile of subtleties  we won t actually compute sqrt number    Instead  we can just check that i i  lt   number   int IsPrime int number        int i      for  i 2  i i lt  number  i              if  number   i    0  return 0            return 1      One last thing  though  there was a small bug in your original algorithm   If number is negative  or zero  or one  this function will claim that the number is prime   You likely want to handle that properly  and you may want to make number be unsigned  since you re more likely to care about positive values only   int IsPrime unsigned int number        if  number  lt   1  return 0     zero and one are not prime     unsigned int i      for  i 2  i i lt  number  i              if  number   i    0  return 0            return 1      This definitely isn t the fastest way to check if a number is prime  but it works  and it s pretty straightforward   We barely had to modify your code at all

User · Answer

Stephen Canon answered it very well   But   The algorithm can be improved further by observing that all primes are of the form 6k    1  with the exception of 2 and 3   This is because all integers can be expressed as  6k   i  for some integer k and for i   -1  0  1  2  3  or 4  2 divides  6k   0    6k   2    6k   4   and 3 divides  6k   3    So a more efficient method is to test if n is divisible by 2 or 3  then to check through all the numbers of form 6k    1   vn  This is 3 times as fast as testing all m up to vn   int IsPrime unsigned int number        if  number  lt   3  amp  amp  number  gt  1           return 1                as 2 and 3 are prime     else if  number 2  0    number 3  0           return 0         check if number is divisible by 2 or 3     else           unsigned int i          for  i 5  i i lt  number  i  6                if  number   i    0    number  i   2     0                   return 0                    return 1

User · Answer

this program is much efficient for checking a single number for primality check   bool check int n       if  n  lt   3            return n  gt  1             if  n   2    0    n   3    0            return false                int sq sqrt n     include math h or use i i lt n in for loop     for  int i   5  i lt  sq  i    6            if  n   i    0    n    i   2     0                return false                       return true

User · Answer

Avoid overflow bug  unsigned i  number      for  i 2  i i lt  number  i          Buggy for  i 2  i i lt  number  i    2        Buggy    or for  i 5  i i lt  number  i  6       Buggy   These forms are incorrect when number is a prime and i i is near the max value of the type   Problem exists with all integer types  signed  unsigned and wider   Example   Let UINT MAX SQRT as the floor of the square root of the maximum integer value   E g  65535 when unsigned is 32-bit   With for  i 2  i i lt  number  i     this 10-year old failure occurs because when UINT MAX SQRT UINT MAX SQRT  lt   number and number is a prime  the next iteration results in a multiplication overflow   Had the type been a signed type  the overflow is UB   With unsigned types  this itself is not UB  yet logic has broken down   Interations continue until a truncated product exceeds number   An incorrect result may occur   With 32-bit unsigned  try 4 294 967 291  which is a prime   If some integer type MAX been a Mersenne Prime  i i lt  number is never true     To avoid this bug  consider  that number i  number i is efficient on many compilers as the calculations of the quotient and remainder are done together  thus incurring no extra cost to do both vs  just 1   A simple full-range solution   bool IsPrime unsigned number        for unsigned i   2  i  lt   number i  i             if number   i    0               return false                      return number  gt   2

User · Answer

Check the modulus of each integer from 2 up to the root of the number you re checking   If modulus equals zero then it s not prime   pseudo code   bool IsPrime int target      for  i   2  i  lt   root target   i            if   target mod i     0              return false               return true

User · Answer

I would just add that no even number  bar 2  can be a prime number  This results in another condition prior to for loop  So the end code should look like this   int IsPrime unsigned int number        if  number  lt   1  return 0     zero and one are not prime     if   number  gt  2   amp  amp    number   2     0   return 0    no even number is prime number  bar 2      unsigned int i      for  i 2  i i lt  number  i              if  number   i    0  return 0            return 1

User · Answer

I m suprised that no one mentioned this    Use the Sieve Of Eratosthenes   Details     Basically nonprime numbers are divisible by another number besides 1 and themselves Therefore  a nonprime number will be a product of prime numbers     The sieve of Eratosthenes finds a prime number and stores it  When a new number is checked for primeness all of the previous primes are checked against the know prime list    Reasons    This algorithm problem is known as  Embarrassingly Parallel  It creates a collection of prime numbers Its an example of a dynamic programming problem Its quick

User · Answer

Using Sieve of Eratosthenes  computation is quite faster compare to  known-wide  prime numbers algorithm   By using pseudocode from it s wiki  https   en wikipedia org wiki Sieve of Eratosthenes   I be able to have the solution on C    public bool IsPrimeNumber int val           Using Sieve of Eratosthenes      if  val  lt  2                return false                Reserve place for val   1 and set with true      var mark   new bool val   1       for var i   2  i  lt   val  i                  mark i    true                Iterate from 2     sqrt val       for  var i   2  i  lt   Math Sqrt val   i                  if  mark i                            Cross out every i-th number in the places after i  all the multiples of i               for  var j    i   i   j  lt   val  j    i                                mark j    false                                     return mark val       IsPrimeNumber 1000000000  takes 21s 758ms   NOTE  Value might vary depend on hardware specifications

User · Answer

After reading this question  I was intrigued by the fact that some answers offered optimization by running a loop with multiples of 2 3 6   So I create a new function with the same idea  but with multiples of 2 3 5 30   int check235 unsigned long n        unsigned long sq  i       if n lt  3  n  5          return n gt 1       if n 2  0    n 3  0    n 5  0          return 0       if n lt  30          return checkprime n      use another simplified function         sq ceil sqrt n        for i 7  i lt  sq  i  30          if  n i  0    n  i 4   0    n  i 6   0    n  i 10   0    n  i 12   0                n  i 16   0    n  i 22   0    n  i 24   0              return 0           return 1      By running both functions and checking times I could state that this function is really faster  Lets see 2 tests with 2 different primes     time   testprimebool x 18446744069414584321 0 f 2 3  Yes  its prime      real    0m14 090s user    0m14 096s sys     0m0 000s    time   testprimebool x 18446744069414584321 1 f 2 3 5  Yes  its prime      real    0m9 961s user    0m9 964s sys     0m0 000s    time   testprimebool x 18446744065119617029 0 f 2 3  Yes  its prime      real    0m13 990s user    0m13 996s sys     0m0 004s    time   testprimebool x 18446744065119617029 1 f 2 3 5  Yes  its prime      real    0m10 077s user    0m10 068s sys     0m0 004s   So I thought  would someone gain too much if generalized  I came up with a function that will do a siege first to clean a given list of primordial primes  and then use this list to calculate the bigger one   int checkn unsigned long n  unsigned long  p  unsigned long t        unsigned long sq  i  j  qt 1  rt 0      unsigned long  q   r       if n lt 2          return 0       for i 0  i lt t  i                  if n p i   0              return 0          qt  p i             qt--       if n lt  qt          return checkprime n      use another simplified function         if  q calloc qt  sizeof unsigned long     NULL                perror  q calloc              exit 1             for i 0  i lt t  i            for j p i -2  j lt qt  j  p i               q j  1       for j 0  j lt qt  j            if q j               rt         rt qt-rt      if  r malloc sizeof unsigned long  rt    NULL                perror  r malloc              exit 1             i 0      for j 0  j lt qt  j            if  q j               r i    j 1       free q        sq ceil sqrt n        for i 1  i lt  sq  i  qt 1                if i  1  amp  amp  n i  0              return 0          for j 0  j lt rt  j                if n  i r j    0                  return 0            return 1      I assume I did not optimize the code  but it s fair  Now  the tests  Because so many dynamic memory  I expected the list 2 3 5 to be a little slower than the 2 3 5 hard-coded  But it was ok as you can see bellow  After that  time got smaller and smaller  culminating the best list to be      2 3 5 7 11 13 17 19   With 8 6 seconds  So if someone would create a hardcoded program that makes use of such technique I would suggest use the list 2 3 and 5  because the gain is not that big  But also  if willing to code  this list is ok  Problem is you cannot state all cases without a loop  or your code would be very big  There would be 1658879 ORs  that is    in the respective internal if   The next list      2 3 5 7 11 13 17 19 23   time started to get bigger  with 13 seconds  Here the whole test     time   testprimebool x 18446744065119617029 2 3 5 f 2 3 5  Yes  its prime  real    0m12 668s user    0m12 680s sys     0m0 000s    time   testprimebool x 18446744065119617029 2 3 5 7 f 2 3 5 7  Yes  its prime  real    0m10 889s user    0m10 900s sys     0m0 000s    time   testprimebool x 18446744065119617029 2 3 5 7 11 f 2 3 5 7 11  Yes  its prime  real    0m10 021s user    0m10 028s sys     0m0 000s    time   testprimebool x 18446744065119617029 2 3 5 7 11 13 f 2 3 5 7 11 13  Yes  its prime  real    0m9 351s user    0m9 356s sys     0m0 004s    time   testprimebool x 18446744065119617029 2 3 5 7 11 13 17 f 2 3 5 7 11 13 17  Yes  its prime  real    0m8 802s user    0m8 800s sys     0m0 008s    time   testprimebool x 18446744065119617029 2 3 5 7 11 13 17 19 f 2 3 5 7 11 13 17 19  Yes  its prime  real    0m8 614s user    0m8 564s sys     0m0 052s    time   testprimebool x 18446744065119617029 2 3 5 7 11 13 17 19 23 f 2 3 5 7 11 13 17 19 23  Yes  its prime  real    0m13 013s user    0m12 520s sys     0m0 504s    time   testprimebool x 18446744065119617029 2 3 5 7 11 13 17 19 23 29 f 2 3 5 7 11 13 17 19 23 29                                                                                                                           q calloc    Cannot allocate memory     PS  I did not free r  intentionally  giving this task to the OS  as the memory would be freed as soon as the program exited  to gain some time  But it would be wise to free it if you intend to keep running your code after the calculation     BONUS  int check2357 unsigned long n        unsigned long sq  i       if n lt  3  n  5  n  7          return n gt 1       if n 2  0    n 3  0    n 5  0    n 7  0          return 0       if n lt  210          return checkprime n      use another simplified function         sq ceil sqrt n        for i 11  i lt  sq  i  210                    if n i  0    n  i 2   0    n  i 6   0    n  i 8   0    n  i 12   0        n  i 18   0    n  i 20   0    n  i 26   0    n  i 30   0    n  i 32   0        n  i 36   0    n  i 42   0    n  i 48   0    n  i 50   0    n  i 56   0        n  i 60   0    n  i 62   0    n  i 68   0    n  i 72   0    n  i 78   0        n  i 86   0    n  i 90   0    n  i 92   0    n  i 96   0    n  i 98   0        n  i 102   0    n  i 110   0    n  i 116   0    n  i 120   0    n  i 126   0        n  i 128   0    n  i 132   0    n  i 138   0    n  i 140   0    n  i 146   0        n  i 152   0    n  i 156   0    n  i 158   0    n  i 162   0    n  i 168   0        n  i 170   0    n  i 176   0    n  i 180   0    n  i 182   0    n  i 186   0        n  i 188   0    n  i 198   0              return 0            return 1      Time     time   testprimebool x 18446744065119617029 7 h 2 3 5 7  Yes  its prime  real    0m9 123s user    0m9 132s sys     0m0 000s

User · Answer

int is prime int val       int div square      if  val  2  return TRUE        2 is prime       if   val amp 1   0  return FALSE        any other even number is not        div 3     square 9        3 3       while  square lt val            if  val   div    0  return FALSE        evenly divisible         div  2       square div div          if  square  val  return FALSE     return TRUE      Handling of 2 and even numbers are kept out of the main loop which only handles odd numbers divided by odd numbers  This is because an odd number modulo an even number will always give a non-zero answer which makes those tests redundant  Or  to put it another way  an odd number may be evenly divisible by another odd number but never by an even number  E E  E  E O  E  O E  E and O O  O    A division modulus is really costly on the x86 architecture although how costly varies  see http   gmplib org  tege x86-timing pdf   Multiplications on the other hand are quite cheap

[c#] C - determine if a number is prime

Examples related to c#

Examples related to c

Examples related to primes