Quicker Prime Number Test

When you search manually, you can search for every odd number that is a step of 2. If you're a bit more clever (as you are), you can use steps of 6 (2 * 3). Testing (testno+1)%6==0 is very similar to (testno % 6) = 5. You can speed up big time by having a loop that increments per steps of 6.

// you meant to use && here not ||
if ((testno % 2 != 0) && (testno % 3 != 0) && (testno % 5 != 0))
{
  for(i=6;i*i <= testno; i+=6)
  {
    if ((testno % (i + 1) == 0)
      || (testno % (i + 5) == 0))
    {
      printf("\nNot Prime");
      getch();
      exit();
    }
}
else
{
   printf("\nNot Prime");
   getch();
   exit();
}

If you're a computer, you can take steps of (2*3*5)=30 or even perhaps (2*3*5*7)=210. For 30, initially you have to check for multiples of 2 3 5 7 11 13 17 19 23 29. Then, if this pass, you can do 30k+1 30k+7 30k+11 30k+13 30k+17 30k+19 30k+23 30k+29 This is saving you a lot of tests. With your method, you'd do: 6k-1 6k+1 05 07 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 61 With steps of 30, you avoid 25 35 55.