C++ Program hangs when calling a function

Question

I have written a code which checks whether a integer is prime or not,whenever i am calling that function the command line just hangs. I am using MingW in Windows 7

#include<iostream>
#include<math.h>
using namespace std;
bool checkPrime(int n);
int main()
{
    int t,tempstart;
    cout<<checkPrime(6);
    return 0;
}
bool checkPrime(int n)
{
    bool check=true;
    for (int i = 0; i <(int) sqrt(n) ; i++)
    {
        if(n%i==0)
        {
            check=false;
            cout<<"asas";
            break;
        }
    }
    return check;
}

Answer 1

it should not hang-up at least not for n=6

1.try this

• instead of:

  if(n%i==0) 
  

• write:

  if((n%i)==0) 
  

• some compilers do a mess with multi operation conditions so bracketing usually helps

2.as mentioned i should go from 2

• n%0 is division by zero maybe your code thrown hidden exception and that is what is wrong

3.have you try to debug it ?

• get a breakpoint inside for loop and step it and see why it is not stopping when i==2,3

Tips for speeding it up a little (just few thousand times for bigger n)

1.i=2,3,5,7,9,11,13,...

• as mentioned in comments do i=2 separately (by (n&1)==0 instead of (n%2)==0)

• and the rest:

  for (nn=sqrt(n),i=3;i<=nn;i+=2) ...
  

2.instead of sqrt(n) use number with the half of bits

3.do not compute sqrt inside for (some compilers do not pre-compute)

4.use sieve of Aristoteles

• create one or more arrays which will eliminate few divisions from you
• do not forget to use array size as common multiply of dividers inside it
• this is what can speed up things considerably
• because it can eliminate many for cycles with a single array access
• but it need initialization of arrays prior to their use

• for example array

  BYTE sieve[4106301>>1]; //only odd numbers are important so the size is half and each bit hold one sieve value so the size is really 4106301*8 which is divided by:
  

• can hold sieves for dividers:

• 3,5,7,11,13,17,19,23,137,131,127,113,83,61,107,101,
• 103,67,37,41,43,53,59,97,89,109,79,73,71,31,29

5.divide by primes

• you can remember first M primes in some array (for example first 100 primes)
• and divide by them

• and the use

  for (nn=sqrt(n),i=last prime+2;i<=nn;i++) ...
  

• also you can remember all primes computed on runtime in some list and use them

6.you can combine all above all together

7.there are many other ways to improve performance of is_prime(n) ?

• so study if you need more speed

Answer 2

According to the operator precedence in C++ % has more priority than == so you should be using

if((n%i)==0)

good luck!