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!