[C#] Algoritmo per numeri primi

[Sensei89]

ciao ragazzi ho un problemino riguardo l'implementazione di un "setaccio" per numeri primi.
ecco il codice:

using System;
using System.Collections;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.IO;
using System.Windows.Forms;

namespace WindowsFormsApplication1
{
    public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();
        }

        private void CrivelloDiEratostene(int LimiteInferiore, int LimiteSuperiore)
        {
            ArrayList Crivello = new ArrayList(LimiteSuperiore - (LimiteInferiore-1));

            /*Inserisce i valori dell'intervallo immesso all'interno dell'ArrayList*/
            LimiteInferiore = Int32.Parse(textBox1.Text);
            for (int i = 0; i < Crivello.Capacity; i++)
            {
                Crivello.Add(LimiteInferiore);
                LimiteInferiore++;
            }

            textBox1.Text = null;
            textBox2.Text = null;

            /*Elimina 0 e 1 dalla lista*/

                if ((int)Crivello[0] == 1)
                    Crivello.RemoveAt(0);
                if ((int)Crivello[0] == 0 && (int)Crivello[1] == 1)
                {
                    Crivello.RemoveAt(0);
                    Crivello.RemoveAt(0);
                }

                for (int i = 0; i < Crivello.Count; i++)
                {
                    for (int j = 1; j < Crivello.Count; j++)
                    {
                        if ((int)Crivello[i] % (int)Crivello[j] > 0)
                            Crivello.RemoveAt(j);
                    }
                }

            /*Stampa il contenuto dell'ArrayList su un file txt*/
            const string FileName = "Elenco_Numeri_Primi.txt";
            using (StreamWriter sw = File.CreateText(FileName))
            {
                sw.WriteLine("Elenco Numeri Primi");
                sw.WriteLine();
                for (int i = 0; i < Crivello.Count; i++)
                {
                    sw.WriteLine(Crivello[i]);
                }
                sw.Close();
            }
        }

        private void button1_Click(object sender, EventArgs e)
        {
            CrivelloDiEratostene(Int32.Parse(textBox1.Text), Int32.Parse(textBox2.Text));
        }
    }
}

Il problema è nei due for nidificati, dove in teoria dovrei controllare i multipli del primo elemento dell'array ed eliminarli e così via.
ad esempio, se come intervallo inserisco 2 e 6 mi stampa sul file txt solamente 2 e 4... quando in realtà dovrebbe stamparmi 2 3 5.
Penso che il problema riguardi proprio la rimozione dell'indice dell'array, in quanto ogni volta viene ricompattato e quindi con gli indici dei for prefissati in quel modo lo scorro in modo errato... potreste consigliarmi un metodo migliore per farlo o come correggere questo mio errore?

[escocat]

Io nel secondo ciclo non dividerei l'elementi i-esimo per l'elemento j-esimo della lista, ma l'elemento i-esimo proprio per il valore del contatore j che dovrebbe andare da 2 al valore dell'elemento i-esimo MENO 1.

[escocat]

Non so per esempio guarda questo algoritmo (l'ho fatto di getto quindi attenzione)

For i = 1 To 100
    primo = 1
    For j = 2 To n(i) - 1
        If n(i) % j = 0 Then primo = 0: Exit For
    Next j
    If primo = 1 Then MsgBox Str(n(i)) + " è primo!"
Next i

....che poi, detto tra noi, viste le premesse non ci sarebbe bisogno nemmeno del primo array

[Sensei89]

Originariamente inviato da escocat
Io nel secondo ciclo non dividerei l'elementi i-esimo per l'elemento j-esimo della lista, ma l'elemento i-esimo proprio per il valore del contatore j che dovrebbe andare da 2 al valore dell'elemento i-esimo MENO 1.

Non ho capito l'esempio
In ogni caso non capisco ciò che intendi: nel primo for inizializzo i = 1 , mentre nel secondo inizializzo j = 2.
poi se faccio la divisione dell'elemento j-esimo della lista per il contatore j, al primo passaggio verrebbe già un risultato maggiore del limite superiore del for... o sbaglio?.. dato che va da 2 a i-1

[escocat]

Ricominciamo tutto d'accapo
Nel tuo codice usi una lista (una specie di array) però poi vuoi esplorare una successione di numeri interi consecutivi da un estremo inferiore ad un estremo superiore. A te quale problema interessa? Un intervallo di numeri consecutivi (e allora non c'è bisogno di una lista) oppure numeri a casaccio (tipo random o inseriti da tastiera; in questo caso ci vuole la lista)?

[Sensei89]

Originariamente inviato da escocat
Ricominciamo tutto d'accapo
Nel tuo codice usi una lista (una specie di array) però poi vuoi esplorare una successione di numeri interi consecutivi da un estremo inferiore ad un estremo superiore. A te quale problema interessa? Un intervallo di numeri consecutivi (e allora non c'è bisogno di una lista) oppure numeri a casaccio (tipo random o inseriti da tastiera; in questo caso ci vuole la lista)?

Il problema che devo risolvere è il seguente:
Chiedo all'utente di passarmi un intervallo di numeri naturali, (ad esempio da 1 a 50) tramite due textBox.. ed il software dovrebbe stampare su un txt i numeri primi contenuti nel dato intervallo.
Pensavo di utilizzare una lista perchè l'algoritmo prevede l'eliminazione dei multipli del primo numero (in questo caso 2) fino a quando il quadrato del numero è maggiore del limite superiore passato dall'utente.
Per questo motivo pensavo di utilizzare un arraylist, dal quale via via elimino i vari multipli in modo molto comodo, col metodo RemoveAt.
a fine programma (in teoria lol) dovrebbero rimanermi solamente i numeri primi contenuti nell'intervallo, che io stamperò sul file di testo...

[escocat]

Originariamente inviato da Sensei89
...l'algoritmo prevede l'eliminazione dei multipli del primo numero (in questo caso 2) fino a quando il quadrato del numero è maggiore del limite superiore passato dall'utente.

"l'algoritmo prevede" nel senso che nessun algoritmo di ricerca dei numeri primi in un intervallo può fare a meno di questo passaggio oppure nel senso che l'esercizio che devi svolgere ti impone questo passaggio? No perchè io questa complicazione non la vedo necessaria...(e non ho nemmeno capito bene la sua necessità ...)
Se io ti dicessi che puoi trovare tutti i numeri primi in un intervallo di valori consecutivi senza usare alcuna lista o array tu saresti contento o no?

[escocat]

Non è che, per caso, quel "passaggio" ti serve per escludere tutti i numeri pari? A maggior ragione l'array non serve....

[Andrea Simonassi]

Originariamente inviato da Sensei89
ciao ragazzi ho un problemino riguardo l'implementazione di un "setaccio" per numeri primi.
ecco il codice:

Penso che il problema riguardi proprio la rimozione dell'indice dell'array, in quanto ogni volta viene ricompattato e quindi con gli indici dei for prefissati in quel modo lo scorro in modo errato... potreste consigliarmi un metodo migliore per farlo o come correggere questo mio errore?

Ogni volta che rimuovi dovresti decrementare j.

se infatti rimuovi l'elemento j-esimo l'elemento corrente e incrementi anche j salti un elemento

for (int i = 0; i < Crivello.Count; i++)
{
	for (int j = 1; j < Crivello.Count; j++)
	{
		if ((int)Crivello[i] % (int)Crivello[j] > 0)
		{
                	Crivello.RemoveAt(j);
			j--;
		}
	}
}

[Andrea Simonassi]

ah, poi j va inizializzato a i+1 non ad 1, infine il modulo deve essere = 0 per potere cancellare un elemento (non > 0) e il modulo va invertito, non è un operazione commutativa... a%b != b%a, infine una volta che l'elemento i-esimo ^2 > elemento maggiore non vale la pena continuare a iterare , infatti se ho un numero a che è il numero piu alto della lista, se questo non è primo deve essere, come minimo, formato dal prodotto di due numeri primi, una qualche composizione di p*q , ora siccome tutti i multipli dei numeri primi minori dell'elemento i-esimo sono stati eliminati il minimo valore di p e q deve essere elemento[i] , quindi una volta che il crivello ha raggiunto la radice quadra dell'elemento massimo il suo lavoro è finito, con questa semplice ottimizzazione il loop piu esterno (i) nel caso del calcolo tra 1 e 10000 esegue 25 volte invece di 10mila.

 for (int i = 0; i < Crivello.Count  && (int)Crivello[i] * (int)Crivello[i] < (int)Crivello[Crivello.Count -1]; i++)
{
     for (int j = i+1; j < Crivello.Count; j++)
     {
         if ((int)Crivello[j] % (int)Crivello[i] == 0)
             Crivello.RemoveAt(j--);
      }
}