[C++] Sito Erastotenesa przy użyciu std::list

[punk_koper]

Witam, muszę napisać sito Eratostenesa, korzystając z kontenera std::list. Wydawało mi się to stosunkowo proste, program jednak nie działa. Byłbym wdzięczny, gdyby ktoś wskazał błąd w moim kodzie.

Kod: Zaznacz cały

#include <cstdlib>
#include <iostream>
#include <math.h>
#include <list>
using namespace std;

int main(int argc, char *argv[])
{   int l,i,k,m,n=2;
    cin >> l;
    list<int> lista;
    for(i=0;i<l;i++)
    {lista.push_back(i+1);}
    for(k=2;k<=sqrt(l);k++)
          {    while(k*n<=l)
             
             lista.remove(k*n);
             n++;                       
          }
    list<int>::iterator iter;
    for(iter=lista.begin(); iter != lista.end(); iter++ )

    cout<<*iter<<" ";
    system("PAUSE");
    return EXIT_SUCCESS;
}

[chlorofil]

Poprawiony kod:

Kod: Zaznacz cały

void sito(int l)
{   
    int i,k,m,n=2;
    list<int> lista;
    for(i=1;i<l;i++)
    {
        lista.push_back(i+1);
    }
    for(k=2;k<=sqrt((double)l);k++)
    {
        n = 2;
        while(k*n<=l)
        {
            lista.remove(k * n);
            n++;                       
        }
    }
    list<int>::iterator iter;
    for(iter=lista.begin(); iter != lista.end(); iter++)
        cout << *iter << " ";
}

Teraz musisz tylko wywołać tę funkcję w main().

Główny błąd w Twoim kodzie polegał na tym, że zapominałeś o "odnowieniu" zmiennej \(\displaystyle{ n}\) przy usuwaniu kolejnych czynników.

[Afish]

Kod: Zaznacz cały

for(k=2;k<=sqrt(l);k++)
          {    while(k*n<=l)
             
             lista.remove(k*n);
             n++;                       
          }

Brakuje klamry po while'u (w pętli wykonuje się tylko jedna instrukcja), poza tym nigdzie nie jest ustawiana wartość n, przez co jest ona niepoprawna przy kolejnej iteracji pętli for.
Poza tym zamiast math.h dołączaj cmath.

[Xitami]

zamiast

Kod: Zaznacz cały

for(k=2;k<=sqrt((double)l);k++)

ładniej

Kod: Zaznacz cały

for( k=2; k*k <= l; k++ )  // zwykle lepsze niż k<=wcześniej_wyliczony_pierwiastek

zamiast

Kod: Zaznacz cały

n=2; while (...) {...}

eleganciej

Kod: Zaznacz cały

for( n=k*k ; n<=l ; n+=k )  lista.remove(n);

[Mariusz M]

Xitami, problem w tym że w informatyce mamy do czynienia z podzbiorem liczb całkowitych
tj mamy określoną liczbę bitów na których możemy zapisać liczbę całkowitą np
liczba 32 bitowa lub liczba 64 bitowa i dlatego jest dość duże prawdopodobieństwo
że przekroczymy zakres liczby całkowitej zapisując pętlę w ten sposób