Esercizio in c++
Fiorenzo Morini
Creare un programma che mostri in una finestra Dos tutti i numeri primi
usando 2 For Loops e "%".
Come posso risolverlo??
Grazie!
Enrico Maria Giordano
Mi sa che mostrare "tutti" i numeri primi è un po' difficile...
EMG
Ertai
essendo infiniti, comunque il concetto del programma è questo: diciamo che
devi trovare i numeri primi tra i primi N numeri naturali. Ogni numero
naturale (primo for) lo provi a dividere per ciascuno dei numeri naturali a
lui inferiori (secondo for) e attraverso l'operatore % scopri se la
divisione è possibile( N%numero == 0) oppure no. Se quel numero non è
divisibile per *nessun* numero naturale inferiore a lui, hai trovato per
definizione un numero primo e lo stampi.
Ovviamenti questo algoritmo si può migliorare, ma questo metodo 'brute'
funzia sempre.
Non te lo implemento, altrimenti, che razza di esercizio diventa poi? ;)
Fiorenzo Morini <f.mo...@bluewin.ch> wrote in message
889kdc$872$1...@bw107zhb.bluewin.ch...
> Leggendo un libro mi é capitato l'esercizio:
>
> Creare un programma che mostri in una finestra Dos tutti i numeri primi
> usando 2 For Loops e "%".
> Come posso risolverlo??
>
>
>
Colin McAllister
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
. x x x x x x x x
x croce ogni 2
. x x x x x
ogni 3
. x x x
x
. x x
x 5
. [...]
i numeri primi non hanno croci sotto di loro!
l'algoritmo è una cazzata da fare
se ti sono stato di aiuto rispondimi via email
studi ing?
Colin McAllister
Il Ghenio
<f.mo...@bluewin.ch> wrote:
>Creare un programma che mostri in una finestra Dos tutti i numeri primi
>usando 2 For Loops e "%".
Mostrare tutti i numeri primi é una cosa impossibile, perché sono
infiniti. Casomai puoi realizzare un programma che trova N numeri
primi , e non si tratta di un algoritmo molto difficile da realizzare.
>Come posso risolverlo??
Con qualcosa di questo tipo:
#define quantita 1000
int main(void)
{
int x,y;
bool primo;
for(x=1; x<=quantita; x++)
{
primo=true;
for(y=x-1 ;y>1 ;y--) if(x % y == 0) primo=false;
if(primo==true)cout<<x<<" é un numero primo.\n";
else cout<<x<<" non é un numero primo.\n";
}
return 0;
}
Ciao!!
Il Ghenio
-----
James: Finalmente so cosa provano i panni messi in lavatrice!
Jesse: Avremo bisogno di un candeggio!!
(Team Rocket)
-----
Nicola Musatti
continua a emettere numeri primi...
Ciao,
Nicola
fau...@a.invalid
>...
> devi trovare i numeri primi tra i primi N numeri naturali. Ogni numero
> naturale (primo for) lo provi a dividere per ciascuno dei numeri naturali a
> lui inferiori (secondo for) e attraverso l'operatore % scopri se la
fino a sqrt(N) , se tieni memoria dei numeri primi gia` trovati e dividi
solo per questi "fai prima"
--
Fausto Petraccone <fpetrac...@tiscalinet.it>
Available PGP RSA\DSS\ElGamal keys
Nicola Musatti
fau...@a.invalid wrote:
>
[...]
> fino a sqrt(N) , se tieni memoria dei numeri primi gia` trovati e dividi
> solo per questi "fai prima"
Vero, ma verificare questo vincolo puo' essere molto "costoso" rispetto
agli altri passi dell'algoritmo. Altro miglioramento e' che basta
dividere per i primi gia' trovati, non e' necessario farlo per tutti i
numeri naturali.
A proposito, qualcuno sa descrivere una versione dell'algoritmo che non
sfrutti un numero N, limite superiore dell'insieme dei numeri primi da
trovare (ad es. "trova tutti i primi inferiori a N=1000), ovvero che
possa girare indefinitamente continuando a emettere primi (tralasciando
evidentemente i problemi di overflow della rappresentazione numerica e/o
di spazio di memoria).
Incrementare N periodicamente non vale...
Ciao,
Nicola
Guido Gagliardi
Nicola Musatti wrote:
Se tu riuscissi a fare questo avresti una formula di generazione di un numero
arbitrario di numeri primi. E probabilmente diventeresti il piu' ricco e
famoso matematico del mondo.
Al momento non esiste un algoritmo di generazione di un numero arbitrario di
numeri primi, neanche "asciando buchi in mezzo", cioe' non richiedendo di
trovare tutti i numero primi in un determinato intervallo, ma solo un
sottoinsieme.
Comunque non voglio smontarti, prova e magari ci riesci!
>
> Ciao,
> Nicola
Alex Martelli
news:38BA6751...@divalsim.it...
[snip]
> Vero, ma verificare questo vincolo puo' essere molto "costoso" rispetto
> agli altri passi dell'algoritmo. Altro miglioramento e' che basta
> dividere per i primi gia' trovati, non e' necessario farlo per tutti i
> numeri naturali.
>
> A proposito, qualcuno sa descrivere una versione dell'algoritmo che non
> sfrutti un numero N, limite superiore dell'insieme dei numeri primi da
> trovare (ad es. "trova tutti i primi inferiori a N=1000), ovvero che
> possa girare indefinitamente continuando a emettere primi (tralasciando
> evidentemente i problemi di overflow della rappresentazione numerica e/o
> di spazio di memoria).
> Incrementare N periodicamente non vale...
Senza nessuna ottimizzazione, neppure quelle ovvie, ecco un approccio:
typedef std::vector<int> v;
void trova_un_altro_primo(v& primi)
{
int candidato = primi.empty()?2:primi.back()+1;
for(;;) {
v::iterator it=primi.begin();
while(it != primi.end() && (candidato%*it) != 0)
++it;
if(it == primi.end()) {
primi.push_back(candidato);
return;
}
++candidato;
}
}
void emetti_infiniti_primi()
{
v primi;
for(;;) {
trova_un_altro_primo(primi);
std::cout<<primi.back()<<'\n';
}
}
Fra le ottimizzazioni piu` ovvie c'e` quella di avere
1, 2 e 3 come primi "built-in" (da inserire all'inizio,
prima del ciclo di chiamate a trova_un_altro_primo,
nel vettore primi) e sostituire "++candidato" con
"candidatp+=2".
Altra potenziale ottimizzazione e` sostituire il while,
in trova_un_altro_primo, con:
while(it != primi.end()) {
int n = *it;
if(n*n > candidato) {
it = primi.end();
} else {
if(candidato%n) break;
}
}
E ce ne sono ovviamente molte altre.
Alex
Alex Martelli
news:38BA6BC0...@ge.infn.it...
[snip]
> Se tu riuscissi a fare questo avresti una formula di generazione di un
numero
> arbitrario di numeri primi. E probabilmente diventeresti il piu' ricco e
> famoso matematico del mondo.
???
> Al momento non esiste un algoritmo di generazione di un numero arbitrario
di
> numeri primi, neanche "asciando buchi in mezzo", cioe' non richiedendo di
> trovare tutti i numero primi in un determinato intervallo, ma solo un
> sottoinsieme.
??? ??? ???
Non esistono algoritmi *con caratteristiche di prestazioni particolarmente
buone* per svolgere questo compito. Un algoritmo O(sqrt(N)) per controllare
se un certo numero N e` primo ovviamente esiste, e quindi esiste anche
un algoritmo O(N alla 1.5) per emettere tutti e soli i numeri primi in un
intervallo [1..N] (questo nell'ipotesi comune che le operazioni aritmetiche
elementari su di un numero richiedano tempo costante; per numeri con
quantita` illimitata di cifre, e` piu` ragionevole dire che ogni operazione
aritmetica su di un numero O(N) e` un algoritmo O(log N), quindi l'intero
algoritmo triviale e` O(log N per N alla 1.5)).
Faccio notare che non ho visto in questo thread nessuna specifica relativa
alle prestazioni degli algoritmi desiderati... l'ultima volta che si parlava
di
prestazioni di algoritmi a livello O(), si trattava di NP-completi, NP-hard
e
simili (e l'algoritmo suddetto e` ovviamente polinomiale...!-).
Alex
Nicola Musatti
realta' mi ero fissato (se si puo' chiamare fissazione qualcosa che mi
impegna per qualche secondo al mese...) sull'idea di generalizzare il
"crivello di Eratostene" intercalando i cicli sui primi gia' trovati con
un approccio tipo diagonalizzazione. Non sono del tutto sicuro che si
riesca, pero'.
Ciao,
Nicola
Alex Martelli
Ci si potrebbe anche riuscire (in un modello astratto a memoria
infinita, ma con tempo di esecuzione bounded).
Il concetto-base per inquadrare questo approccio e` quello
di "stream" -- non nel senso C++ ma in quello piu` classico
meravigliosamente illustrato ad esempio nell'Abelson e
Sussman, "Structure and Interpretation of Computer
Programs".
Uno "stream" e` un "flusso" (monodirezionale) di oggetti
che e` in grado di:
-- presentarmi un "oggetto corrente"
-- avanzare al successivo
-- (solo per stream finiti): dirmi se e` finito
Si potrebbe quindi modellare in C++ come:
template <class T>
class astream: {
public:
virtual constT& current() const = 0;
virtual void next() = 0;
virtual bool finished() const = 0;
};
Ogni volta che trovo un numero primo, posso associare
ad esso un astream<int> con l'ulteriore interessante
proprieta` che i valori successivamente ritornati sono
strettamente crescenti:
class nonprimes_stream: public astream<int> {
int multiple;
int currenti;
public:
nonprimes_stream(int prime): multiple(prime) {
currenti = prime+prime;
}
const int& current() const { return currenti; }
void next() { currenti += multiple; }
bool finished() const { return false; }
};
Usero` spesso l'abbreviazione np_s nel seguito
per indicare un nonprimes_stream.
Anche la successione dei "candidati" puo` essere
ben modellata da un astream<int>, che torna uno
dopo l'altro tutti gli interi positivi.
Dato tutto questo, vogliamo un astream<int> che
torni i soli _numeri primi_ -- come?
Alla "next", otterremo un candidato e lo sottoporremo
al "crivello" di tutti i nonprimes_stream sinora generati.
Se il candidato e` _piu` piccolo_ del current di un certo
nonprimes_stream, allora il candidato e` ancora "vivo"
(e il nonprimes_stream non va alterato).
Se il candidato e` _eguale_ al current di un certo np_s,
il candidato e` "morto" (va rifiutato), e il nonprimes_stream
va fatto passare al suo elemento successivo.
Se il candidato e` _maggiore_ del current di un certo
np_s, quel np_s va fatto avanzare sinche` non si
verifica una delle due condizioni precedenti (e va
compiuta l'azione relativa: accettazione o rifiuto, e
ulteriore avanzamento o meno del np_s).
Ogni candidato va passato al vaglio di tutti i np_s
sinche`: (a) sono stati tutti usati e nessuno ha
rifiutato il candidato o (b) uno qualsiasi rifiuta il
candidato (e` interessante dimostrare che nel caso
b non siamo tenuti a completare il ciclo!).
Nel caso (a), accettiamo il candidato, lo poniamo
come current dell'astream<int> dei numeri primi,
e aggiungiamo il np_s su di lui costruito alla bag
dei np_s che stiamo usando.
Nel caso (b), passiamo al candidato successivo e
ripetiamo il ciclo.
La dimostrazione di correttezza e` interessante (e
si fa molto piu` agevolmente usando notazione piu`
astratta per gli stream).
Ancora piu` interessante e` dimostrare in che senso
questo E` in effetti una generalizzazione del crivello
di Eratostene: un c.d.E-sino-a-N per un certo N
finito si potrebbe indifferentemente implementare
con questo algoritmo _O_ pompando sino alla fine
ciascun np_s appena generato (e ricordando i
risultati in un vettore di bit...); la sequenza di operazioni
richieste ad ogni dato np_s *non cambia* (cambia
solo lo "interleaving" delle operazioni su np_s
disgiunti!).
La differenza e` che con questo ordinamento delle
operazioni non c'e` necessita` di pre-specificare N,
per cui (se avessimo infinita memoria per tenere
tutti i np_s nella nostra bag, e i nostri int fossero
ovviamente a illimitate cifre) avremmo effettivamente
soddisfatto le specifiche (stream infinito dei primi).
Da un punto di vista di correttezza (e di prestazioni
nel senso suddetto) l'ordine dei test di un candidato
rispetto ai vari np_s e` arbitrario (una "grab-bag"
e` la "struttura-dati" adeguata per tenere i np_s).
E` facile dimostrare che nessun np_s puo` essere
omesso (in quanto l'np_s centrato sul numero
primo N e` l'unico in grado di "eliminare" i vari
candidati della forma N**x per x>1... le potenze
del numero primo N).
Alex
Guido Gagliardi
Alex Martelli wrote:
> Guido Gagliardi <Guido.G...@ge.infn.it> wrote in message
> news:38BA6BC0...@ge.infn.it...
> [snip]
> > Se tu riuscissi a fare questo avresti una formula di generazione di un
> numero
> > arbitrario di numeri primi. E probabilmente diventeresti il piu' ricco e
> > famoso matematico del mondo.
>
> ???
>
> > Al momento non esiste un algoritmo di generazione di un numero arbitrario
> di
> > numeri primi, neanche "asciando buchi in mezzo", cioe' non richiedendo di
> > trovare tutti i numero primi in un determinato intervallo, ma solo un
> > sottoinsieme.
>
> ??? ??? ???
>
> Non esistono algoritmi *con caratteristiche di prestazioni particolarmente
> buone* per svolgere questo compito. Un algoritmo O(sqrt(N)) per controllare
> se un certo numero N e` primo ovviamente esiste, e quindi esiste anche
> un algoritmo O(N alla 1.5) per emettere tutti e soli i numeri primi in un
> intervallo [1..N] (questo nell'ipotesi comune che le operazioni aritmetiche
> elementari su di un numero richiedano tempo costante; per numeri con
> quantita` illimitata di cifre, e` piu` ragionevole dire che ogni operazione
> aritmetica su di un numero O(N) e` un algoritmo O(log N), quindi l'intero
> algoritmo triviale e` O(log N per N alla 1.5)).
OK, credevo che fosse chiaro quello che intendevo, pero' rileggendo mi
rendo conto che la mia affermazione e' deboluccia...
Quello che intendevo dire e' che non esiste una formula generatrice di numeri
primi fino a N che, in un senso molto lato, prescinda dalle conoscenze estratte
dai numeri fino a sqrt(N). Sto parlando di formule del tipo n^3 + n^2 +1 (valida
per n = 1, n = 2, n = 3, ma fallace miseramente per n = 4)
Credevo che, visto la diffusione anche divulgativa dell'argomento, fosse piu'
chiaro quello di cui stavo parlando.
Alex Martelli
[snip]
> Quello che intendevo dire e' che non esiste una formula generatrice di
numeri
> primi fino a N che, in un senso molto lato, prescinda dalle conoscenze
estratte
> dai numeri fino a sqrt(N). Sto parlando di formule del tipo n^3 + n^2 +1
(valida
> per n = 1, n = 2, n = 3, ma fallace miseramente per n = 4)
Scusa, ma trovo il senso "troppo" lato. Certo, non posso scrivere un
polinomio in N che generi solo numeri primi... e allora???
Dato un qualsiasi N, posso verificare se sia o meno primo "prescindendo"
da checcessia -- semplicemente provando se e` divisibile per qualsiasi
altro numero, con al massimo O(sqrt(N)) prove di divisione, ognuna
delle quali (per N con numero illimitato di cifre) e` O(log(N)).
Quindi, esiste (ed e` banale) un *algoritmo* generatore. Cosa sia una
"formula", e quali algoritmi siano formule e quali no, non saprei proprio;
se hai definizioni precise di cosa intendi, apprezzerei sentirle.
(Ci sono naturalmente altri approcci, basati su test di primalita` non
esaustivi, che permettono di asserire che N e` "primo con probabilita`
1 - epsilon", per un qualsiasi epsilon prefissato, con una velocita`
enormemente superiore a O(sqrt(N) per log(N))).
> Credevo che, visto la diffusione anche divulgativa dell'argomento, fosse
piu'
> chiaro quello di cui stavo parlando.
Il tema e` quello di trovare ALGORITMI per generare i numeri
primi (NON "formule" per idem, qualsiasi cosa significhi "formule"),
quindi non mi e` _ancora_ chiaro di cosa tu stia parlando.
Alex