С ++ сито Эратосфена с массивом
Я хотел бы закодировать знаменитое Сито Эратосфена в C ++, используя только массив, так как это был бы набор, в котором я мог бы удалить некоторые элементы на пути, чтобы узнать числа простых чисел.
Я не хочу использовать STL (вектор, набор) … Просто массив! Как я могу это понять?
Я пытаюсь объяснить, почему я не хочу использовать оператор множеств STL: я изучаю C ++ с самого начала, и я думаю, что STL, конечно, полезен для программистов, но построен на стандартной библиотеке, поэтому я хотел бы использовать бывшие операторы и команды. Я знаю, что с STL все может быть проще.
Решение
Ключ к сито ЭратосфенаЭффективность в том, что это не так, повторяю не, удалить ⁄ удалить ⁄ выбросить ⁄ и т. д. композиты, перечисляя их, но вместо этого просто Метки их как таковых.
Сохранение всех чисел сохраняет нашу способность использовать значение числа в качестве его адреса в этом массиве и, таким образом, напрямую обращаться к нему: array[n], Это то, что делает подсчет сита и разметку кратных каждого простого числа эффективными при реализации на современном оперативная память компьютеры (так же, как с алгоритмы целочисленной сортировки).
Чтобы этот массив имитировал набор, мы присваиваем каждой записи два возможных значения, флаги: on а также off, prime или же composite, 1 или же 0, Да, нам нужен только один немного, не байт, чтобы представить каждое число в массиве сит, предоставлена мы не удаляем ни одного из них во время работы над ним.
И, кстати, vector<bool> автоматически упаковывается, представляя boolпо битам. Очень удобно.
Другие решения
От Алгоритмы и структуры данных
#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
void runEratosthenesSieve(int upperBound) {
int upperBoundSquareRoot = (int)sqrt((double)upperBound);
bool *isComposite = new bool[upperBound + 1];
memset(isComposite, 0, sizeof(bool) * (upperBound + 1));
for (int m = 2; m <= upperBoundSquareRoot; m++) {
if (!isComposite[m]) {
cout << m << " ";
for (int k = m * m; k <= upperBound; k += m)
isComposite[k] = true;
}
}
for (int m = upperBoundSquareRoot; m <= upperBound; m++)
if (!isComposite[m])
cout << m << " ";
delete [] isComposite;
}int main()
{
runEratosthenesSieve(1000);
}
Вы не хотите использовать STL, но это не очень хорошая идея
STL делает жизнь намного проще.
Еще рассмотрим эту реализацию, используя std::map
int max = 100;
S sieve;
for(int it=2;it < max;++it)
sieve.insert(it);
for(S::iterator it = sieve.begin();it != sieve.end();++it)
{
int prime = *it;
S::iterator x = it;
++x;
while(x != sieve.end())
if (((*x) % prime) == 0)
sieve.erase(x++);
else
++x;
}
for(S::iterator it = sieve.begin();it != sieve.end();++it)
std::cout<<*it<<std::endl;