Алгоритм "Решето Эратосфена"

@CyberGenius · Регистрация: 23.08.2012

Author24 — интернет-сервис помощи студентам

Вот наконец-то получилось реализовать это алгоритм. Укажите, пожалуйста, как можно написать красивее и рациональней?

C++

vector<int> all;//Здесь храняться все числа от 0 до n
    int n= 0; //верхний предел
    int p = 2; //первое простое число
    cin>>n;
 
    for(int i = 0; i<=n; ++i){//Заполнение вектора all
        all.push_back(i);
    }
 
    while(p*p<n){
 
        for(int i = p; i<=n - p; i +=p ){//Заполнение нулями чисел кратных p
            all[i + p] = 0;//Чтобы не заполнять число равное all[i]
        }
    
        int k = p;//НУжно сохранить значение р, т.к дальше в цикле оно изменяется, а нужно использовать имено это значение
 
        for(int i = n; i>=k+1; --i){//Проходим весь вектор и если all[i] не равно 0, то присваеваем р его значение.
            //К+1 используем для того, чтобы не записать в р уже использованое значение
            //т.е чтобы алгоритм опять не просчитывался при р=2; 
 
            if(all[i]!=0){
                p =all[i];
            }
        }
    }
 
    for(int i = 2; i<=n; ++i){//Опять проходим весь вектор и выводим все all[i] не равные 0
        if(all[i]!=0){
            cout<<all[i]<<endl;
        }
    }

@sovaz1997 · 14.12.2012, 17:37

Использовать iterator

@CyberGenius · 14.12.2012, 17:38 **[ТС]**

Сообщение от sovaz1997

Использовать iterator

А что такое iterator, я пока не знаю

@sovaz1997 CEO SOVAZ Corp. 386 / 232 / 51 Регистрация: 17.12.2011 Сообщений: 822 Записей в блоге: 1
	14.12.2012, 17:37	2
	Использовать iterator 0

@CyberGenius 1 / 1 / 1 Регистрация: 23.08.2012 Сообщений: 100
	14.12.2012, 17:38 [ТС]	3
	Сообщение от sovaz1997 Использовать iterator А что такое iterator, я пока не знаю 0