Programma in C piccolo teorema di Fermat

Messaggioda Buraka » 16/10/2019, 20:37

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!
Buraka
New Member
New Member
 
Messaggio: 5 di 60
Iscritto il: 26/08/2019, 18:17

Re: Programma in C piccolo teorema di Fermat

Messaggioda niccoset » 16/10/2019, 23:14

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.
" Tutto dovrebbe essere reso più semplice possibile, ma non più semplice ancora. " - Albert Einstein
niccoset
Average Member
Average Member
 
Messaggio: 282 di 584
Iscritto il: 13/06/2013, 07:17

Re: Programma in C piccolo teorema di Fermat

Messaggioda vict85 » 17/10/2019, 08:25

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.
vict85
Moderatore
Moderatore
 
Messaggio: 9889 di 19253
Iscritto il: 16/01/2008, 00:13
Località: Berlin

Re: Programma in C piccolo teorema di Fermat

Messaggioda Buraka » 18/10/2019, 09:41

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?
Buraka
New Member
New Member
 
Messaggio: 6 di 60
Iscritto il: 26/08/2019, 18:17

Re: Programma in C piccolo teorema di Fermat

Messaggioda vict85 » 18/10/2019, 10:19

Che hai messo i printf nel loop.
vict85
Moderatore
Moderatore
 
Messaggio: 9895 di 19253
Iscritto il: 16/01/2008, 00:13
Località: Berlin


Torna a Informatica

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite