Blog del corso di Programmazione (9 CFU) tenuto da Marco La Cascia presso la sede di Agrigento dell'Universita' di Palermo per il corso di laurea in Ingegneria Gestionale e Informatica. Tratta la programmazione a oggetti in C++.
Buonasera, ho implementato così l'esercizio 11 dell'esercitazione 2:
#include #include
/* Returns the smallest divisor of the input unsigned number. If it is prime, it returns 0. */ unsigned long smallestDivisor(unsigned long number){ unsigned long max_possible_divisor = sqrt(number), increment = 1;
for (unsigned long i = 2; i <= max_possible_divisor; i+=increment){
if (number%i == 0){ return i; } if (i == 3){ increment++; } } return 0; }
bool isPrime(unsigned long number){ if (smallestDivisor(number)){ return true; }else{ return false; } }
int main(){ unsigned long number, divisor;
std::cout<<"Insert a number: "; std::cin>>number;
divisor = smallestDivisor(number); if(divisor){ std::cout<<number<<" isn't a prime. it is divided by "<<divisor<<std::endl; }else{ std::cout<<number<<" is a prime.\n"; } return 0; }
Come ottimizzazioni ho inserito soltanto la limitazione nella ricerca dei divisori fino alla radice quadrata del numero, e l'incremento di due invece che di uno (salta i numeri pari oltre il due). Ho anche un altro dubbio: si può considerare corretta la conversione implicita da double a unsigned long nell'assegnazione? Grazie in anticipo
int main() { unsigned long n; unsigned i, ret, max_divisor;
std::cout << "Inserisci un numero intero: "; std::cin >> n;
ret = n % 2;
if(n != 2 && ret == 0){ std::cout << "Il numero " << n << " non è primo, è divisibile per 2" << std::endl; return 0; }else{ i= 3; max_divisor = sqrt(n); while(i <= max_divisor && ret != 0){ ret = n % i; if(ret == 0){ std::cout << "Il numero " << n << " non è primo, è divisibile per " << i << std::endl; return 0; }else{ i++; } }
std::cout << "Il numero " << n << " è primo" << std::endl; return 0; } }
Grazie per la risposta. Ho un altro dubbio: dato che non abbiamo ancora introdotto gli array dinamici, è scorretto in C++ utilizzare array aventi come dimensione una variabile?
Ho provato a implementare il Crivello. Il programma è strutturato così:
- c'è una funzione che esclude i numeri pari.
http://goo.gl/WrGGzj
- e poi il crivello vero e proprio:
http://goo.gl/QJnVJO
Due domande: 1) è corretto usare "using namespace std;" a inizio file per programmi piccoli? O è meglio evitare? 2) Esiste un modo per terminare il main da un'altra funzione?
using namespace std in generale va evitato ma per implementare l'esercitazione non ci sono problemi. L'importante è evitare di prendere cattive abitudini. Per terminare il programma mentre sei in un'altra funziona il return ovviamente non funziona perche' ti fa tornare al main quindi l'unico modo è usare la funzione di libreria exit o abort (puoi trovare documentazione online).
Buonasera,
RispondiEliminaho implementato così l'esercizio 11 dell'esercitazione 2:
#include
#include
/* Returns the smallest divisor of the input unsigned number. If it is prime, it returns 0.
*/
unsigned long
smallestDivisor(unsigned long number){
unsigned long max_possible_divisor = sqrt(number), increment = 1;
for (unsigned long i = 2; i <= max_possible_divisor; i+=increment){
if (number%i == 0){
return i;
}
if (i == 3){
increment++;
}
}
return 0;
}
bool
isPrime(unsigned long number){
if (smallestDivisor(number)){
return true;
}else{
return false;
}
}
int
main(){
unsigned long number, divisor;
std::cout<<"Insert a number: ";
std::cin>>number;
divisor = smallestDivisor(number);
if(divisor){
std::cout<<number<<" isn't a prime. it is divided by "<<divisor<<std::endl;
}else{
std::cout<<number<<" is a prime.\n";
}
return 0;
}
Come ottimizzazioni ho inserito soltanto la limitazione nella ricerca dei divisori fino alla radice quadrata del numero, e l'incremento di due invece che di uno (salta i numeri pari oltre il due).
Ho anche un altro dubbio: si può considerare corretta la conversione implicita da double a unsigned long nell'assegnazione?
Grazie in anticipo
Come ottimizzazioni 'semplici' più di questo non si può fare. La conversione implicita in questo caso e' sicura.
Eliminaun'altra possibile implementazione:
RispondiElimina#include
#include
int main()
{
unsigned long n;
unsigned i, ret, max_divisor;
std::cout << "Inserisci un numero intero: ";
std::cin >> n;
ret = n % 2;
if(n != 2 && ret == 0){
std::cout << "Il numero " << n << " non è primo, è divisibile per 2" << std::endl;
return 0;
}else{
i= 3;
max_divisor = sqrt(n);
while(i <= max_divisor && ret != 0){
ret = n % i;
if(ret == 0){
std::cout << "Il numero " << n << " non è primo, è divisibile per " << i << std::endl;
return 0;
}else{
i++;
}
}
std::cout << "Il numero " << n << " è primo" << std::endl;
return 0;
}
}
Anche questa va bene. Fa qualche controllo non necessario in più rispetto alla soluzione proposta sopra dal tuo collega ma il risultato e' lo stesso.
EliminaSe cercate una soluzione più efficiente provate con l'algoritmo chiamato 'crivello di eratostene' (potete cercarlo con google).
RispondiEliminaGrazie per la risposta. Ho un altro dubbio: dato che non abbiamo ancora introdotto gli array dinamici, è scorretto in C++ utilizzare array aventi come dimensione una variabile?
EliminaAssolutamente scorretto. Vedremo prestissimo il modo giusto di operare...
EliminaQuesto commento è stato eliminato dall'autore.
RispondiEliminaQuesto commento è stato eliminato dall'autore.
RispondiEliminaHo provato a implementare il Crivello.
RispondiEliminaIl programma è strutturato così:
- c'è una funzione che esclude i numeri pari.
http://goo.gl/WrGGzj
- e poi il crivello vero e proprio:
http://goo.gl/QJnVJO
Due domande: 1) è corretto usare "using namespace std;" a inizio file per programmi piccoli? O è meglio evitare? 2) Esiste un modo per terminare il main da un'altra funzione?
using namespace std in generale va evitato ma per implementare l'esercitazione non ci sono problemi. L'importante è evitare di prendere cattive abitudini.
EliminaPer terminare il programma mentre sei in un'altra funziona il return ovviamente non funziona perche' ti fa tornare al main quindi l'unico modo è usare la funzione di libreria exit o abort (puoi trovare documentazione online).