RISOLTO Algoritmo per verificare se un numero è primo

[Innominato00]

Salve, ho creato un programma che verifica se un numero naturale inserito da tastiera è primo, sapete come un modo per non fare eseguire la divisione più volte se un numero risulta essere primo? Non so se sono stato chiarissimo, in pratica se inserisco 359, lui esegue 357 calcoli, e sono tanti, sapete come rimediare?

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
   float reale;
   int N;

   do
   {
      cout << "Inserire un numero: ";
      cin >> reale;
      N = reale;
   }
   while(!(N == reale && N > 0));

   int divisione = 2;
   bool primo = true;

   while(divisione < N)
   {
         if(N%divisione == 0)
         {
            primo = false;
            break;
         }
      divisione++;
   }

   if(primo)
      cout << endl << N << " e primo " << endl;
   else
      cout << endl << N << " non e primo " << endl;

}

 

[fabio93]

Guarda qui: https://www.tomshw.it/forum/threads/numero-primo.688373/

 

[BAT]

Vedi il mio intervento qui:
https://www.tomshw.it/forum/threads/numero-primo.688373/#post-6645134

 

[Hobet]

Salve, ho creato un programma che verifica se un numero naturale inserito da tastiera è primo, sapete come un modo per non fare eseguire la divisione più volte se un numero risulta essere primo? Non so se sono stato chiarissimo, in pratica se inserisco 359, lui esegue 357 calcoli, e sono tanti, sapete come rimediare?

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
   float reale;
   int N;

   do
   {
      cout << "Inserire un numero: ";
      cin >> reale;
      N = reale;
   }
   while(!(N == reale && N > 0));

   int divisione = 2;
   bool primo = true;

   while(divisione < N)
   {
         if(N%divisione == 0)
         {
            primo = false;
            break;
         }
      divisione++;
   }

   if(primo)
      cout << endl << N << " e primo " << endl;
   else
      cout << endl << N << " non e primo " << endl;

}

Tralasciando quello che ha scritto BAT00cent che è corretto, un approccio divertente è questo sotto che ho scritto ma purtroppo è errato per via degli pseudoprimi. Divertente perchè devi azzeccarcelo lo pseudoprimo essendo un test probabilistico :)

unsigned long long primo(unsigned long long n){
return ( (pow(2,n) - 2) % n == 0) ? 1 : 0;
}

 

[BAT]

un approccio divertente è questo sotto che ho scritto ma purtroppo è errato per via degli pseudoprimi.

Pseudoprimi a parte, il vero problema è che usi l'elevamento a potenza 2^n (2 elevato ad n). La crescita esponenziale incenerisce il tipo unsigned long long in un batter d'occhio: per esempio con n=65537 (che è un numero primo davvero piccolo) ti ritrovi a calcolare 2^65537 che ha 19729 cifre.
Considera che un valore tipico massimo di un unsigned long long a 64 bit è 2^64-1 = 18446744073709551615 (20 cifre)
Questo approccio (teoricamente interessante) finisce col rendere ingestibile anche il controllo su numeri primi piccoli come 65537 che col metodo "classico" (seppur inefficiente) del controllo dei divisori dispari fino alla radice quadrata richiede circa 128 divisioni.