Esercizio con true false

[MPG]

Dato un parametro intero, la funzione restituisce true se esso è primo, false altrimenti.
Cosa ne pensate?

#include <iostream>

using namespace std;
bool flag= true;
int verificaPrimo(int n)

{

if(n%2!=0)
{
return flag;
}
else
{
flag = false;
return flag;
}

}

int main()
{
int numero;
cin>>numero;
verificaPrimo(numero);
cout<<flag;



    return 0;

}

 

[Tidus88]

Direi che questa parte:

if(n%2!=0)
{
    return flag;
}

Non corrisponde correttamente al concetto di n. primo.

Es: 9 non è un numero primo, eppure il tuo programma direbbe di sì, poichè la divisione per 2 darebbe resto diverso da 0.

Secondo me l'unico modo che hai per verificare se un numero è primo è quello di eseguire un ciclo for con i che va da 2 ad n-1 e verificare se n%i da sempre resto != 0.
Prima però sarà il caso di verificare che n sia > 2 (altrimenti è necessariamente primo)

Mi viene da pensare (ma è un'idea che non ho verificato e che probabilmente è matematicamente errata) che il tuo ciclo potrebbe anche andare da 2 ad n/2

 

[MPG]

Ho letto di uso della sqrt per il numero primo tipo
int radice=sqrt(n);
pero' non so bene usarla in questo caso...

 

[Tidus88]

Sì, ho letto anche io.
Il ciclo For dovrebbe andare da 2 a ceiling( sqrt(n) ) (ovvero la radice di n arrotondata per eccesso)

Esistono poi moltissimi altri metodi matematici più sofisticati, diciamo che questo che stiamo tentando è molto tendente al brute force :D

 

[dgcross]

in realtà basta radice n arrotondata per difetto :)

 

[Mursey]

flag dichiarato all'esterno di verificaPrimo non si può vedere però :nono:
fai un vero ritorno di funzione

 

[MPG]

A dir la verità ho trovato qualcosa tipo questo:

bool verificaPrimalita(int n)
{
   int radice=sqrt(n);
   int div=2;

   while(div<=radice)
   {
       if(n%div==0)
        return false;
     div++;
   }
   return true;
}

ma non riesco bene a capire.. aiuti sempre bene accetti ....

 

[dgcross]

sì che poi è proprio brute force... una volta verificato che non è divisibile per 2 puoi banalmente controllare solo per i divisori dispari dimezzando il tempo che ci impiega a fare il ciclo while...

A dir la verità ho trovato qualcosa tipo questo:

bool verificaPrimalita(int n)
{
   int radice=sqrt(n);
   int div=2;

   while(div<=radice)
   {
       if(n%div==0)
        return false;
     div++;
   }
   return true;
}

ma non riesco bene a capire.. aiuti sempre bene accetti ....

inizializza il divisore a 2, poi inizia a ciclare controllando se è divisibile per il divisore: se sì ti ritorna falso, se no incrementa divisore di 1 e ricontrolla.
se a fine ciclo non ha mai trovato un divisore ritorna vero

 

[Tidus88]

Beh, è un po' come fare il for che dicevamo prima.

Lui parte da 2, per ogni valore di div prova a vedere se il resto della divisione con n è == 0.
Se questo si verifica evidentemente il numero non è primo, quindi ritorna direttamente false.
Altrimenti incrementa di 1 div e ripete l'iterazione fino a che div non sia > di radice (sqrt(n)).

Se termina tutte le iterazioni senza che sia mai verificata la condizione n%div == 0 allora esce dal while e a quel punto ritorna true.

 

[MPG]

Quindi cosi' va bene?
Ma non riesco a capire pero' sempre si usa sqrt(n) ......

#include <cstdlib>
#include <ctime>
#include <cmath>
#include <iostream>
using namespace std;

bool verificaPrimalita(int n)
{
   int radice=sqrt(n);
   int div=2;

   while(div<=radice)
   {
       if(n%div==0)
        return false;
     div++;
   }
   return true;
}

int main ()
    {
    int n;
    cin>>n;
    cout<<verificaPrimalita(n)<<endl;
    return 0;
}

 

[rctimelines]

Direi che questa parte:

if(n%2!=0)
{
return flag;
}

Non corrisponde correttamente al concetto di n. primo.

Es: 9 non è un numero primo, eppure il tuo programma direbbe di sì, poichè la divisione per 2 darebbe resto diverso da 0.

Secondo me l'unico modo che hai per verificare se un numero è primo è quello di eseguire un ciclo for con i che va da 2 ad n-1 e verificare se n%i da sempre resto != 0.
Prima però sarà il caso di verificare che n sia > 2 (altrimenti è necessariamente primo)

Mi viene da pensare (ma è un'idea che non ho verificato e che probabilmente è matematicamente errata) che il tuo ciclo potrebbe anche andare da 2 ad n/2

9 non è un numero primo

In ogni caso, meglio che studiate un po' di matematica oltre a tentare di programmare queste cose banali: mai sentito parlare del "crivello di Eratostene"?

Magari trovare i numeri primi fosse così semplice.. o anche no, visto che su questi si basano i sistemi di crittografia. Un numero primo è un intero divisibile solo per 1 e per sé stesso.

Inviato dal mio Nexus 5 utilizzando Tapatalk

 

[MPG]

9 non è un numero primo

In ogni caso, meglio che studiate un po' di matematica oltre a tentare di programmare queste cose banali: mai sentito parlare del "crivello di Eratostene"?

Inviato dal mio Nexus 5 utilizzando Tapatalk

So cos'è il numero primo ci mancherebbe.. poi è tutto banale per chi ha dimestichezza nella materia (oltre che arrivarci prima non tutti siamo uguali...).
Comunque è un po' esagerato permettimi di dare quasi dell'ignorante a chi chiede aiuto....
Se so so benissimo l'inglese e tu chiedessi sul forum delle domande in merito all'inglese non ti risponderei "meglio che studi" ma cerco di aiutarti anche se per me la domanda è banale...

 

[rctimelines]

La radice quadrata non serve a niente. Per verificare che un numero sia primo e quindi assegnare la variabile non serve dividere il numero per tutti i numeri precedenti, ma puoi evitare la divisione per i multipli, basta verificare la divisione senza resto solo per i numeri primi precedenti.
Tieni presente che, a parte 1, anche 2 e 3 sono numeri primi!

Inviato dal mio Nexus 5 utilizzando Tapatalk

 

[MPG]

La radice quadrata non serve a niente. Per verificare che un numero sia primo e quindi assegnare la variabile non serve dividere il numero per tutti i numeri precedenti, ma puoi evitare la divisione per i multipli, basta verificare la divisione senza resto solo per i numeri primi precedenti.
Tieni presente che, a parte 1, anche 2 e 3 sono numeri primi!

Inviato dal mio Nexus 5 utilizzando Tapatalk

Per la verità questo
int radice=sqrt(n)

l'ho visto nel programma del professore di informatica.....

 

[rctimelines]

Per la verità questo
int radice=sqrt(n)

l'ho visto in un programma del professore di informatica.....

Quindi? Metti dentro cose a caso perché le vedi qua o là? La radice ti può servire per fare la fattorializzazione (trovare il minimo comune multiplo: algebra di seconda media!). Ma non basta che la radice sia intera.. per esempio 81 dà 9 ed entrambi non sono numeri primi.. oppure 100!

Inviato dal mio Nexus 5 utilizzando Tapatalk