C++ Creare array di numeri primi

[Miss_Joy]

Salve a tutti,
ho problemi con l'implementazione dell'algoritmo del crivello di Eratostene.

Mi si chiede di creare un array di primi 100 numeri primi e mi risulta parecchio difficile. Posto il codice scritto finora anche se non è completo.

//Programma che determina i primi 100 numeri primi
#include <iostream> 
#include <stdlib.h> 
#include <iomanip> 
using namespace std; 
int main () {
 const int size = 100;
 int a[size]; 
for(int i=1;i<=size;i++){ //creo array di elementi inizializzati a 1 
a[i]=1; 
for(int j=2;j<=size;j++){ //j setaccia l'array
 if(j%i==0){ //cerca i numeri primi 
a[j]=0; // e pone gli elementi dell'array pari a zero se sono multipli
 }
 }
 cout << setw(7) <<i << setw(13) << a[i] <<endl; 
} 
system("Pause"); 
return 0; 
}

Praticamente non riesco nemmeno a cercare gli elementi dell'array che hanno per indici i numeri primi per poi compattarlo. Il problema, credo, sia nella condizione del ciclo for controllato da j.. .
Cos'è che mi sfugge??

[MdE2005]

Ma il problema qual'è? I risultati sono errati? Vengono sollevate delle eccezioni?

Chiarisci meglio il problema riscontrato.

[oregon]

Solo per tua informazione ... gli indici degli array vanno da 0 a size-1 e non da 1 a size

[MdE2005]

Piccolo esempio trovato nel mio archivio (non so se è personale, cioè implementato da me direttamente oppure se preso da Internet, non mi sembra il mio stile):

#include <stdlib.h>
#include <stdio.h>

#define MAX 100

int main(void) {
  int v[MAX], i, j;

  for (i=2; i<MAX; i++)
    v[i] = 1;
  for (i=2; i<MAX; i++) {
    if (v[i] == 1) {
      printf("%d ", i);
      for (j=2; i*j<MAX; j++)
        v[i*j] = 0;
    }
  }
  printf("\n");
  return(1);
}

[MegaAlchimista]

Ma vuoi i primi 100numeri primi o i numeri primi inclusi fra {0 -100} ?
Perchè da qui sebra che tu voglia tutti i numeri primi <100, non i primi 100 numeri primi

[MegaAlchimista]

Comunque anche io ho scoperto di avere un programma già fatto, sostanzialmente uguale a quello di mde

/*********************************************************************************
** Questo programma calcola tutti i numeri primi < MAX e li salva su un array **
*********************************************************************************/
int main(int argc, char *argv[])
{
int max=100;
char ext='N';
while (ext!='Y')
{
_ std::cout << "inserire il numero massimo entro cui cercare i numeri primi:\n";
_ std::cin >> max;
_ int count=max;
_ int* v = new int[max];
_ for (int i=2; i<max; i++) //inizializzo tutti gli elementi a 1
_ _ v[i] = 1;
_ for (int i=2; i<max; i++)
_ {
_ _ if (v[i] == 1) 
_ _ {
_ _ _ for (int j=2; i*j<max; j++) //se è multiplo di i lo metto a 0
_ _ _ {
_ _ _ _ if(v[i*j]!=0)
_ _ _ _ {
_ _ _ _ _ v[i*j] = 0;
_ _ _ _ _ --count; //conto i numeri primi
_ _ _ _ }
_ _ _ }
_ _ }//end if(v[i]==1)
_ }
_ //salvo i numeri primi (gli indici in cui il valore è !=0) su un array p
_ int* p = new int [count];
_ int indx=0;
_ std::cout <<"\nI numeri primi minori di "<< max << " sono: \n";
_ for(int i=2;i<max;++i)
_ {
_ _ if(v[i]!=0)
_ _ {
_ _ _ *(p+indx)=i;
_ _ _ std::cout << i <<"\n";
_ _ _ ++indx;
_ _ }
_ } 
_ std::cout << "\nCi sono "<< count << " numeri primi.\n";
_ std::cout << "Vuoi uscire? (Y/N) \n";
_ std::cin >> ext;
_ delete[] p;
_ delete[] v;

}//end while
_
return 0;
}

Sper che gli array dinamici non ti confondano (non conosco il tuo livello di studio)

[Miss_Joy]

Mi sono espressa male: l'array deve contenere i numeri primi compresi tra 0 e 100.
Ovviamente escludo lo zero come indice dell'array per evitare la divisione per zero e 1 perché è il divisore comune a tutti i numeri.
Purtroppo non sono pratica di array dinamici, per cui il codice postato da MegaAlchimista non può andare...mi può essere utile, però, per la costruzione del mio codice ma c'è una cosa che vorrei capire : LA CONDIZIONE CHE USI PER TROVARE I NUMERI PRIMI.

for (int j=2; i*j<max; j++) //se è multiplo di i lo metto a 0 
 { 
 if(v[i*j]!=0)
 { 
v[i*j] = 0;

Il problema del mio codice è che alla fine mi dà un array in cui gli elementi sono impostati tutti a zero!
Grazie per le risposte e per l'aiuto che mi state offrendo!

[Miss_Joy]

I passaggi potrebbero essere questi:
1: Creo un array di elementi inizializzati a 1. Gli elementi che hanno per indici dei numeri primi rimangono uguali a 1, gli altri uguali a zero.
2: Parto dall'indice 2
3:Ogni volta che trovo un elemento uguale a 1, cerco i suoi multipli
4:Azzero tutti gli elementi il cui indice è multiplo dell'elemento trovato, escludendo l'elemento trovato.
5:Gli elementi impostati ancora a 1 sono numeri primi, di conseguenza scarto gli elementi che sono stati impostati a 0.

#include <iostream>
#include <stdlib.h>
#include <iomanip>
using namespace std;
int main () {
     const int size =100; // dimensione array
             int a[size];

    //1:Creo array di elementi inizializzati a 1
          for (int i=1;i<size;i++)
             a[i]=1;

    //2 , 3, 4 : Cerco i multipli e li imposto a zero
         for (int i=2;i<size;i++){
             if(a[i]==1){
           for(int j=2;j<size;j++){
               if(i%j==0){
              a[i]=0;    //Come faccio ad escludere l'elemento trovato?
                                              
         }
       }
     }  //se stampo qui, mi dà un array di elementi tutti nulli
   }
    
       
  system("Pause");
   return 0;
}

Nel codice manca la condizione 5, perché con questo codice ottengo un array di 100 elementi impostati a zero.Dov'è l'errore??

[MegaAlchimista]

Originariamente inviato da Miss_Joy
Purtroppo non sono pratica di array dinamici, per cui il codice postato da MegaAlchimista non può andare...mi può essere utile, però, per la costruzione del mio codice ma c'è una cosa che vorrei capire : LA CONDIZIONE CHE USI PER TROVARE I NUMERI PRIMI.

for (int j=2; i*j<max; j++) //se è multiplo di i lo metto a 0 
 { 
 if(v[i*j]!=0)
 { 
v[i*j] = 0;

Il problema del mio codice è che alla fine mi dà un array in cui gli elementi sono impostati tutti a zero!
Grazie per le risposte e per l'aiuto che mi state offrendo!

Qui praticamente tu sei interna a un for che itera i: per ogni valore di i, prendi tutti i valori di j, tutti (j*i) non sono peimi per definizione, allora se (j*i) è minore di max significa che esiste nel tuo aray e lo metti a zero.
Ad esempio se sei ad i=2.
Prendi j=2, trovi 4, che non è primo, e lo metti a zero. Poi prendi j=3, trovi 6, e lo metti a zero. Per j=51 trovi 102 che è maggiore del tuo massimo, quindi esci da questo for ed aumenti i. Adesso i=3, j=2 e ricominci.
Non vorrei ti cofondesse il

if(v[i*j]!=0)

Questo è messo solo perchê io dovevo contare quanti primi c'erano, quindi non dovevo mai passare due volte dallo stesso numero: se l'avevo già messo a zero andavo avanti

Spero di essermi spiegato
In questi modo per i grandi fai pochissime iterazioni e vai più veloce.

Edit:
Detto questo , se nel tuo algoritmo tutti i numeri vengono messi a zero vuol dire che è sbagliato, e la colpa penso che sia di quel i%j (pensaci).
Per il fatto che il tuo array sia di 100elementi non c'è scampo.
Come vedi io avevo contato i numeri primi e li avevo messo nell'array p, ma per farlo devi per forza usare array dinamici in quanto non puoi sapere a prri quanti sono i numeri primi.
Oppure ti fai un altro array di 100elementi, i numeri primi saranno per forza di meno, ci copi tutti i numeri primi da v in modo consecutivo ed il resto li metti a 0

[MdE2005]

Originariamente inviato da Miss_Joy
Mi sono espressa male: l'array deve contenere i numeri primi compresi tra 0 e 100.
Ovviamente escludo lo zero come indice dell'array per evitare la divisione per zero e 1 perché è il divisore comune a tutti i numeri.
Purtroppo non sono pratica di array dinamici, per cui il codice postato da MegaAlchimista non può andare...mi può essere utile, però, per la costruzione del mio codice ma c'è una cosa che vorrei capire : LA CONDIZIONE CHE USI PER TROVARE I NUMERI PRIMI.

for (int j=2; i*j<max; j++) //se è multiplo di i lo metto a 0 
 { 
 if(v[i*j]!=0)
 { 
v[i*j] = 0;

Il problema del mio codice è che alla fine mi dà un array in cui gli elementi sono impostati tutti a zero!
Grazie per le risposte e per l'aiuto che mi state offrendo!

Hai provato la soluzione? Cosa c'è che non va?