why doesn't My C code on Fermat's little theorem run properly after 10?

Question

I am a complete beginner and was just trying to apply what I have learned.

So I tried to make a C program that computes if a number passes the prime test in Fermat's little theorem.

Here is the code:

#include <stdio.h>
#include <math.h>

int main() {
  double p, a, t;
  printf("Enter the number tested to be prime: ");
  scanf("%lf", &p);
  a = 1;
  t = 0;
  while (a <= p && t == 0) {
    t = pow(a, p) - a;
    t = (int)t % (int)p;
    a++;
  }
  if (t == 0) {
    printf("prime test passed");
  } else {
    printf("prime test failed");
  }

  return 0;
}

So the problem is it works great until 10, but after that when I try it for 11 it just fails the test. Why is this happening?

You do know that one of the properties of prime numbers is that they are *integers*? So don't accept floating point value input or use floating point arithmetic or call floating point functions. — Some programmer dude, Aug 20 '21 at 14:43
...and (assuming you have fixed that) using `pow` for integer calculations is not a very good idea — Eugene Sh., Aug 20 '21 at 14:44
so can I declare my own power function without the math library and make it accept only integers? — khoprutu, Aug 20 '21 at 14:53
You may want to evaluate that power using modular arithmetic (and a wider type), though, otherwise it will overflow pretty fast. — Bob__, Aug 20 '21 at 15:10

score 1 · Answer 1 · answered Aug 20 '21 at 16:49

for 11 it just fails the test. Why is this happening?

The reason for this concrete failure is likely not due to use of floating point math, but quite the contrary due to use of casting to an integer type by (int)t with a 4-byte int. In the course of your prime test, double t is assigned the value 8¹¹−8 = 8589934584, which can well be held in t, but not in an int with a maximum value of 2³¹−1 = 2147483647.

Of course all this does not mean that you'll get much further if you just take this hurdle; soon you'd really encounter problems of floating point math. So the comment from Bob__ may indeed be a good advice.

why doesn't My C code on Fermat's little theorem run properly after 10?

1 Answers1