[C++] Решето эратосфена, где баг ?

[Silly Student]

Требуется реализовать Решето Эратосфена

Но почемуто вычеркнуть получается только первый элемент (цифра "4").

Делаю так:

//---------------------------------------------------------------------------
#include <iostream.h>
#pragma hdrstop

#include <tchar.h>
//---------------------------------------------------------------------------

#pragma argsused
int _tmain(int argc, _TCHAR* argv[])
{
const int n = 20; //до куда выписываем целые числа
int array[n]={NULL};//массив, заполненный нулями
int p = 2; // первое простое число

//заполняю массив целыми числами от 2 до n

for (int i = 2; i <= n; i++) {
	array[i] = i;
}

//вычеркиваю из списка все числа от 2p до n, делящиеся на p
for (int i = p*2; p <= n;) {
	if (array[i]%p == 0) {
	array[i]=0;
	}
	if (array[i] > p) {
		p=array[i];
	}
		i++;
}
//вывод результата. (всё, что не 0, то простое)
for (int i = 0; i <= n; i++) {
	cout << array[i] << endl;
}
system("PAUSE");
	return 0;
}
//---------------------------------------------------------------------------

Глядя на статью в википедии, мне начинает казаться, что тут нужно вставить еще 1 цикл, но где, и какой ?

[russian-stalker]

Ну я бы сделал так:

#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
    //Алгоритм с википедии
    std::vector<unsigned int> simples;
    unsigned int n = 120;
    //1. Выписать подряд все целые числа от двух до n (2, 3, 4, …, n).
    for (unsigned int i = 2; i <= n; i++)
        simples.insert(simples.end(), i);

    for (std::vector<unsigned int>::iterator i = simples.begin(); i != simples.end(); i++)
    {
        //2. Пусть переменная p изначально равна двум — первому простому числу.
        //Далее будет:
        //4. Найти первое не вычеркнутое число, большее чем p, и присвоить значению переменной p это число.
        int p = *i;
        //3. Вычеркнуть из списка все числа от 2p до n, делящиеся на p (то есть, числа 2p, 3p, 4p, …)
        for (unsigned int j = 2*p; j <= n; j += p)//Каждый шаг прибавляем по p, начиная от 2p. Получается 2p, 3p, etc.
        {
            //Ищем элемент
            std::vector<unsigned int>::iterator item = std::find(simples.begin(), simples.end(), j);
            //Если его нет, то пропускаем
            if (item == simples.end()) continue;
            //Иначе удаляем
            if (j%p == 0)
                simples.erase(item);
        }
        std::cout<<p<<std::endl;
        //5. Повторять шаги 3 и 4 до тех пор, пока p не станет больше, чем n
    }

    //6. Все не вычеркнутые числа в списке — простые числа.
    return 0;
}

[Silly Student]

Чёто сложно. Векторы, итераторы, какието ::

[Silly Student]

Ввёл функцию, и всё заработало ) Они всётаки облегчают жизнь.

//---------------------------------------------------------------------------

#pragma hdrstop
#include <iostream.h>
#include <tchar.h>
//---------------------------------------------------------------------------

#pragma argsused
int func(int); // прототип

int _tmain(int argc, _TCHAR* argv[])
{
int x = 100; //до какого числа надо получить простые

for (int i = 2; i <= x; i++) {
	func(i);
}

system("PAUSE");
	return 0;
}

int func(int n)
{
	//int n=7;
bool prostoe = false;
for (int i = 2; i < n; i++) {
	if (n%i!=0) {
		prostoe=true;
	}
	else {
		prostoe = false;
		break;
	}
}

//
if (prostoe==true) {
	cout << n << "  (prostoe) " << endl;
}
return 0;
}
//---------------------------------------------------------------------------