Esercizio con true false

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

Codice:
#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

Utente Attivo
401
12
Hardware Utente
CPU
AMD Sempron 3000+
Scheda Madre
AsRock K7-880
RAM
DDR 1GB
Scheda Video
Nvidia 6600GT AGP
Scheda Audio
Soundblaster Live! 5.1
#2
Direi che questa parte:


Codice:
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
 

Tidus88

Utente Attivo
401
12
Hardware Utente
CPU
AMD Sempron 3000+
Scheda Madre
AsRock K7-880
RAM
DDR 1GB
Scheda Video
Nvidia 6600GT AGP
Scheda Audio
Soundblaster Live! 5.1
#4
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

Utente Attivo
1,076
263
Hardware Utente
CPU
Ryzen 5 1600 @3,85GHz 1,3V
Dissipatore
EK Supremacy EVO (Alphacool NexXxoS XT45+ST30 360mm)
Scheda Madre
ASRock X370 Gaming K4
Hard Disk
Goodram CX300 480GB + Toshiba P300 3TB
RAM
2x8 G.Skill TridentZ RGB @3066MHz CL14
Scheda Video
2x R9 Nano in CF @1050MHz + liquido custom (Alphacool NexXxoS XT45+ST30 360mm)
Scheda Audio
Sennheiser HD598 SE + Fiio Q1 Mark II + Breeze BA100 + Mission LX-1
Monitor
Samsung U28E590D
Alimentatore
Be Quiet! Power Zone 650W
Case
Fractal Design Define S TG
Periferiche
Ozone Strike Pro Spectra, Steelseries Rival 500, Steam Controller, DualShock4 v2
Sistema Operativo
Windows 10 Pro 64 bit / Ubuntu 18.04 LTS
#5
in realtà basta radice n arrotondata per difetto :)
 
#7
A dir la verità ho trovato qualcosa tipo questo:

Codice:
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

Utente Attivo
1,076
263
Hardware Utente
CPU
Ryzen 5 1600 @3,85GHz 1,3V
Dissipatore
EK Supremacy EVO (Alphacool NexXxoS XT45+ST30 360mm)
Scheda Madre
ASRock X370 Gaming K4
Hard Disk
Goodram CX300 480GB + Toshiba P300 3TB
RAM
2x8 G.Skill TridentZ RGB @3066MHz CL14
Scheda Video
2x R9 Nano in CF @1050MHz + liquido custom (Alphacool NexXxoS XT45+ST30 360mm)
Scheda Audio
Sennheiser HD598 SE + Fiio Q1 Mark II + Breeze BA100 + Mission LX-1
Monitor
Samsung U28E590D
Alimentatore
Be Quiet! Power Zone 650W
Case
Fractal Design Define S TG
Periferiche
Ozone Strike Pro Spectra, Steelseries Rival 500, Steam Controller, DualShock4 v2
Sistema Operativo
Windows 10 Pro 64 bit / Ubuntu 18.04 LTS
#8
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:

Codice:
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

Utente Attivo
401
12
Hardware Utente
CPU
AMD Sempron 3000+
Scheda Madre
AsRock K7-880
RAM
DDR 1GB
Scheda Video
Nvidia 6600GT AGP
Scheda Audio
Soundblaster Live! 5.1
#9
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.
 
#10
Quindi cosi' va bene?
Ma non riesco a capire pero' sempre si usa sqrt(n) ......


Codice:
#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;
}
 
2,791
704
Hardware Utente
CPU
i7 3770
Dissipatore
stock intel
Scheda Madre
Gigabyte GA-H67A-UD3H-B3
Hard Disk
SSD SAMSUNG 850EVO 250GB + HDD WD GREEN CAVIAR 2TB
RAM
16GB = Corsair XMS3 4x4GB DDR3 1600MHz CL9
Scheda Video
ATI Firepro V7900 2GB
Scheda Audio
Soundblaster X-Fi
Monitor
HP 27'' + Benq 19''
Sistema Operativo
Windows10-pro64/OpenSUSE-QL42.3/Manjaro-17.0.2-KDE
#11
Direi che questa parte:


Codice:
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
 
Mi Piace: dgcross
#12
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...
 
Ultima modifica:
2,791
704
Hardware Utente
CPU
i7 3770
Dissipatore
stock intel
Scheda Madre
Gigabyte GA-H67A-UD3H-B3
Hard Disk
SSD SAMSUNG 850EVO 250GB + HDD WD GREEN CAVIAR 2TB
RAM
16GB = Corsair XMS3 4x4GB DDR3 1600MHz CL9
Scheda Video
ATI Firepro V7900 2GB
Scheda Audio
Soundblaster X-Fi
Monitor
HP 27'' + Benq 19''
Sistema Operativo
Windows10-pro64/OpenSUSE-QL42.3/Manjaro-17.0.2-KDE
#13
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
 
#14
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.....
 
Ultima modifica:
2,791
704
Hardware Utente
CPU
i7 3770
Dissipatore
stock intel
Scheda Madre
Gigabyte GA-H67A-UD3H-B3
Hard Disk
SSD SAMSUNG 850EVO 250GB + HDD WD GREEN CAVIAR 2TB
RAM
16GB = Corsair XMS3 4x4GB DDR3 1600MHz CL9
Scheda Video
ATI Firepro V7900 2GB
Scheda Audio
Soundblaster X-Fi
Monitor
HP 27'' + Benq 19''
Sistema Operativo
Windows10-pro64/OpenSUSE-QL42.3/Manjaro-17.0.2-KDE
#15
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