Programma in C piccolo teorema di Fermat

Salve a tutti.
Volevo scrivere un programma in C che verificasse che n sia primo o meno e per questo ho deciso di utilizzare il piccolo teorema di Fermat ovvero:
\(\displaystyle p \) è primo se:
\(\displaystyle a^p \equiv a \left(\mathrm{mod} \ p \right)\), \(\displaystyle \forall a \in \mathbb{Z} \).
Il problema è che per valori grandi (all'incirca da n=40 in su) il programma non da il risultato corretto. Dove sta il problema? Il codice è il seguente:

Codice:

#include<stdio.h>
#include<math.h>
int main ()
{
   int n;
   n=0;
   int a;
   a=2;
   printf("Inserisci il numero\n");
   scanf("%d", &n);
   int m=pow(a,n);
   int k=m-a;
   int t=k%n;
   if (t==0){
      printf ("%d e' un numero primo", n);
   }
   else {
      printf("%d non e' un numero primo", n);
      
   }
   
}

Grazie in anticipo!

In C il tipo int rappresenta un intero con segno e per rappresentare un int vengono utilizzati 4 bytes. È facile vedere quindi che il numero massimo positivo rappresentabile con un int è pari a $ 2147483647 $ (pari a $ 2^31-1 $ ). Questo è il motivo per cui il tuo programma non funziona, puoi fare una prova anche inserendo un numero $ n = 37 $ (che è minore di 40) e renderti conto che non funziona lo stesso.

Il modo per risolvere il problema scritto da niccoset è di fare i calcoli in \(\mathbb{Z}_p\) direttamente, ovvero di evitare la funzione \(pow\) e scrivere una funzione che faccia l'elevamento a potenza in modulo.

Grazie a tutti per le risposte intanto. Ho scritto un altro programma in C che verificasse la primalità di n. Ma anche qui c'è un problema, sicuramente dovuto al codice anziché alla memoria. Ecco qui il codice:

Codice:

#include<stdio.h>
int main(void)
{
   int n=0;
   int k;
   k=2;
   printf("inserisci il numero\n");
   scanf("%d", &n);
   while(k<n){
      if(n%k==0){
         printf("il numero non e' primo");
      }
      else{
         k=k+1;
         if(n%k==0){
            printf("il numero e' primo");
         }
      }
   }
   return 0;
}

Quando il numero n è primo, il programma stampa su video "il numero e' primo". Quando inserisco un numero composto allora stampa su video "il numero non e' primo" in loop. Dove sbaglio?

Che hai messo i printf nel loop.