Determining if a number is prime

Question

I have perused a lot of code on this topic  but most of them produce the numbers that are prime all the way up to the input number   However  I need code which only checks whether the given input number is prime   Here is what I was able to write  but it does not work   void primenumber int number        if number 2  0        cout lt  lt  Number is prime   lt  lt endl      else        cout lt  lt  number is NOt prime  lt  lt endl      I would appreciate if someone could give me advice on how to make this work properly   Update  I modified it to check on all the numbers in a for loop   void primenumber int number        for int i 1  i lt number  i                 if number i  0            cout lt  lt  Number is prime   lt  lt endl         else            cout lt  lt  number is NOt prime  lt  lt endl

User · Answer

Someone above had the following   bool check prime int num    for  int i   num - 1  i  gt  1  i--        if   num   i     0          return false    return true      This mostly worked   I just tested it in Visual Studio 2017   It would say that anything less than 2 was also prime  so 1  0  -1  etc    Here is a slight modification to correct this   bool check prime int number        if  number  gt  1                for  int i   number - 1  i  gt  1  i--                        if   number   i     0                  return false                    return true            return false

User · Answer

If n is 2  it s prime   If n is 1  it s not prime   If n is even  it s not prime   If n is odd  bigger than 2  we must check all odd numbers 3  sqrt n  1  if any of this numbers can divide n  n is not prime  else  n is prime   For better performance i recommend sieve of eratosthenes   Here is the code sample    bool is prime int n      if  n    2  return true    if  n    1    n   2    0  return false     for  int i   3  i i  lt  n 1  i    2          if  n   i    0  return false         return true

User · Answer

My own IsPrime   function  written and based on the deterministic variant of the famous Rabin-Miller algorithm  combined with optimized step brute forcing  giving you one of the fastest prime testing functions out there      int64 power int a  int n  int mod       int64 power a result 1    while n       if n amp 1      result  result power  mod    power  power power  mod    n gt  gt  1      return result     bool witness int a  int n     int t u i     int64 prev curr    u n 2   t 1   while   u amp 1        u  2      t       prev power a u n    for i 1 i lt  t   i       curr  prev prev  n    if  curr  1  amp  amp  prev  1  amp  amp  prev  n-1       return true    prev curr      if curr  1     return true   return false     inline bool IsPrime  int number      if        number  amp  1    amp  amp  number    2       number  lt  2      number   3    0  amp  amp  number    3      return  false     if number lt 1373653       for  int k   1  36 k k-12 k  lt  number   k    if    number    6 k 1     0      number    6 k-1     0       return  false      return true       if number  lt  9080191       if witness 31 number   return false    if witness 73 number   return false    return true        if witness 2 number   return false   if witness 7 number   return false   if witness 61 number   return false   return true      WARNING  Algorithm deterministic only for numbers  lt  4 759 123 141  unsigned int s max is 4294967296     if n  lt  1 373 653  it is enough to test a   2 and 3     if n  lt  9 080 191  it is enough to test a   31 and 73     if n  lt  4 759 123 141  it is enough to test a   2  7  and 61     if n  lt  2 152 302 898 747  it is enough to test a   2  3  5  7  and 11     if n  lt  3 474 749 660 383  it is enough to test a   2  3  5  7  11  and 13     if n  lt  341 550 071 728 321  it is enough to test a   2  3  5  7  11  13  and 17        To use  copy and paste the code into the top of your program  Call it  and it returns a BOOL value  either true or false   if IsPrime number         cout  lt  lt   It s prime      else       cout lt  lt  It s composite       If you get a problem compiling with    int64   replace that with  long   It compiles fine under VS2008 and VS2010   How it works  There are three parts to the function  Part checks to see if it is one of the rare exceptions  negative numbers  1   and intercepts the running of the program   Part two starts if the number is smaller than 1373653  which is the theoretically number where the Rabin Miller algorithm will beat my optimized brute force function  Then comes two levels of Rabin Miller  designed to minimize the number of witnesses needed  As most numbers that you ll be testing are under 4 billion  the probabilistic Rabin-Miller algorithm can be made deterministic by checking witnesses 2  7  and 61  If you need to go over the 4 billion cap  you will need a large number library  and apply a modulus or bit shift modification to the power   function   If you insist on a brute force method  here is just my optimized brute force IsPrime   function   inline bool IsPrime  int number      if        number  amp  1    amp  amp  number    2       number  lt  2      number   3    0  amp  amp  number    3      return  false     for  int k   1  36 k k-12 k  lt  number   k    if    number    6 k 1     0      number    6 k-1     0       return  false     return true         How this brute force piece works  All prime numbers  except 2 and 3  can be expressed in the form 6k 1 or 6k-1  where k is a positive whole number  This code uses this fact  and tests all numbers in the form of 6k 1 or 6k-1 less than the square root of the number in question  This piece is integrated into my larger IsPrime   function  the function shown first     If you need to find all the prime numbers below a number  find all the prime numbers below 1000  look into the Sieve of Eratosthenes  Another favorite of mine   As an additional note  I would love to see anyone implement the Eliptical Curve Method algorithm  been wanting to see that implemented in C   for a while now  I lost my implementation of it  Theoretically  it s even faster than the deterministic Rabin Miller algorithm I implemented  although I m not sure if that s true for numbers under 4 billion

User · Answer

if number 2  0        cout lt  lt  Number is prime   lt  lt endl    The code is incredibly false  33 divided by 2 is 16 with reminder of 1 but it s not a prime number

User · Answer

simple function to determine if a number is a prime number   to state if it is a prime number    include  lt iostream gt   using namespace std    int isPrime int x      functioned defined after int main     int main      int y      cout lt  lt  enter value  lt  lt endl       cin gt  gt y       isPrime y          return 0        end of main function     -------------function    int isPrime int x        int counter  0       cout lt  lt  factors of   lt  lt x lt  lt   are   lt  lt   n n        print factors of the number       for  int i  0  i lt  x  i                   for  int j  0  j lt  x  j                           if  i   j    x         check if the number has multiples                                       cout lt  lt i lt  lt            output provided for the reader to see the                                        muliples                     counter           counts the number of factors                                             cout lt  lt   n n      if counter gt 2                 cout lt  lt  value is not a prime number  lt  lt   n n             if counter lt  2                cout lt  lt  value is a prime number  lt  lt endl

User · Answer

This is a quick efficient one   bool isPrimeNumber int n        int divider   2      while  n   divider    0            divider              if  n    divider            return true            else           return false            It will start finding a divisible number of n  starting by 2  As soon as it finds one  if that number is equal to n then it s prime  otherwise it s not

User · Answer

bool check prime int num        for  int i   num - 1  i  gt  1  i--            if   num   i     0              return false            return true      checks for any number if its a prime number

User · Answer

define TRUE 1  define FALSE -1  int main        Local variables declaration    int num   0  int result   0      Getting number from user for which max prime quadruplet value is  to be found    printf   nEnter the number      scanf   d    amp num    result   Is Prime  num        Printing the result to standard output    if  TRUE    result      printf   n d is a prime number n   num   else     printf   n d is not a prime number n   num    return 0     int Is Prime  int num     int i   0      Checking whether number is negative  If num is negative  making it positive    if  0  gt  num       num   -num      Checking whether number is less than 2    if  2  gt  num       return FALSE      Checking if number is 2    if  2    num       return TRUE      Checking whether number is even  Even numbers are not prime numbers    if  0      num   2        return FALSE      Checking whether the number is divisible by a smaller number 1    2  is done to skip checking divisibility by even numbers  Iteration reduced to half    for  i   3  i  lt  num  i    2       if  0      num   i               Number is divisible by some smaller number           hence not a prime number            return FALSE   return TRUE

User · Answer

Use mathematics first find square root of number then start loop  till the number ends which you get after square rooting  check for each value whether the given number is divisible by the iterating value  if any value divides the given number then it is not a prime number otherwise prime  Here is the code   bool is Prime int n         int square root   sqrt n      use math h    int toggle   1     for int i   2  i  lt   square root  i              if n i  0                  toggle   0          break                  if toggle       return true     else      return false

User · Answer

This code only checks if the number is divisible by two  For a number to be prime  it must not be evenly divisible by all integers less than itself  This can be naively implemented by checking if it is divisible by all integers less than floor sqrt n   in a loop  If you are interested  there are a number of much faster algorithms in existence

User · Answer

I Have Use This Idea For Finding If The No  Is Prime or Not    include  lt conio h gt    include  lt iostream gt  using namespace std  int main       int x  a    cout  lt  lt   Enter The No        cin  gt  gt  x    int prime unsigned int     a   prime x     if  a    1      cout  lt  lt   It Is A Prime No    lt  lt  endl    else   if  a    0      cout  lt  lt   It Is Composite No    lt  lt  endl    getch       int prime unsigned int x      if  x    1        cout  lt  lt   It Is Neither Prime Nor Composite       return 2        if  x    2    x    3    x    5    x    7      return 1    if  x   2    0  amp  amp  x   3    0  amp  amp  x   5    0  amp  amp  x   7    0      return 1    else     return 0

User · Answer

I would guess taking sqrt and running foreach frpm 2 to sqrt 1 if input  number  0  return false  once you reach sqrt 1 you can be sure its prime

User · Answer

bool isPrime int number        if number  lt  2  return false      if number    2  return true      if number   2    0  return false      for int i 3   i i  lt  number  i  2           if number   i    0   return false            return true

User · Answer

I came up with this   int counter   0   bool checkPrime int x       for  int y   x  y  gt  0  y--         if  x y    0             counter                    if  counter    2          counter   0    resets counter for next input       return true    if its only divisible by two numbers  itself and one  its a prime         else counter   0          return false

User · Answer

If you are lazy  and have a lot of RAM  create a sieve of Eratosthenes which is practically a giant array from which you kicked all numbers that are not prime   From then on every prime  probability  test will be super quick  The upper limit for this solution for fast results is the amount of you RAM  The upper limit for this solution for superslow results is your hard disk s capacity

User · Answer

C    bool isPrime int number       if  number    2           if  number  lt  2    number   2    0                return false                    for int i 3   i i  lt  number  i  2               if number   i    0                    return false                                    return true      Javascript  function isPrime number        if  number     2            if  number  lt  2    number   2     0                return false                    for  var i 3   i i  lt  number  i  2                        if  number   2     0                   return false                                    return true      Python  def isPrime number       if  number    2           if  number  lt  2 or number   2    0               return False         i   3         while  i i   lt   number              if number   i    0                    return False              i    2     return True

User · Answer

If you know the range of the inputs  which you do since your function takes an int   you can precompute a table of primes less than or equal to the square root of the max input  2 31-1 in this case   and then test for divisibility by each prime in the table less than or equal to the square root of the number given

User · Answer

There are several different approches to this problem  The  Naive  Method  Try all  odd  numbers up to  the root of  the number  Improved  Naive  Method  Only try every 6n    1  Probabilistic tests  Miller-Rabin  Solovay-Strasse  etc     Which approach suits you depends and what you are doing with the prime  You should atleast read up on Primality Testing

User · Answer

You need to do some more checking  Right now  you are only checking if the number is divisible by 2  Do the same for 2  3  4  5  6      up to number  Hint  use a loop   After you resolve this  try looking for optimizations  Hint  You only have to check all numbers up to the square root of the number

User · Answer

I follow same algorithm but different implementation that loop to sqrt n  with step 2 only odd numbers because I check that if it is divisible by 2 or 2 k it is false  Here is my code   public class PrimeTest        public static boolean isPrime int i            if  i  lt  2                return false            else if  i   2    0  amp  amp  i    2                return false            else               for  int j   3  j  lt   Math sqrt i   j   j   2                    if  i   j    0                        return false                                              return true                                   param args             public static void main String   args            for  int i   1  i  lt  100  i                  if  isPrime i                     System out println i

[c++] Determining if a number is prime

Examples related to c++

Examples related to algorithm

Examples related to primes