Newsgroup: it.comp.lang.c++
Titolo: Esercizio in c++

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??
Grazie!


Mi sa che mostrare "tutti" i numeri primi è un po' difficile...
EMG

la soluzione è quella del CRIVELLO DI ERATOSTENE
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?



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)
-----

Beh, e' possibile scrivere un programma che non termina mai e che
continua a emettere numeri primi...
Ciao,
Nicola


	Available PGP RSA\DSS\ElGamal  keys

 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

 Nicola

 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

 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

Hai perfettamente ragione e, una volta visto, e' piuttosto ovvio. Io in
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

 wrote in message
news:38BA7C77...@divalsim.it...

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

 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.

 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