Programma in C piccolo teorema di Fermat

[Buraka]

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:

#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!

[niccoset]

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.

[vict85]

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.

[Buraka]

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:

#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?

[vict85]

Che hai messo i printf nel loop.