Список сито эратосфена

Question

здесь программа, которая находит первичные числа в массиве от n до 2n. он работает правильно, но что-то должно быть иначе: В этой программе решето накладывается на массив: элементы заменяются нулями. Это должно быть неправильно: массивов нет. Сначала сформируйте список всех номеров один за другим в списке ссылок. Затем удалите из списка те ссылки, которые содержат кратные. В конце распечатайте то, что осталось. IDK, как я могу это сделать без массивов.

#include <iostream>
using namespace std;


struct node 
{
    int num;
    node* next, * prev; 
};

class List  // list
{
    node* head, * tail; 
public:
    List() :head(NULL), tail(NULL) {};
    void Print();
    void Add(int num);
};

void List::Print() //print list
{
    node* temp = head;

    while (temp != NULL)
    {
        cout << temp->num << " ";
        temp = temp->next;
    }
    cout << endl;
}

void List::Add(int num)  //add to list
{
    node* temp = new node;
    temp->next = NULL;
    temp->num = num;
    if (head!=NULL)        
    {
        temp->prev = tail;
        tail->next = temp;
        tail = temp;
    }
    else
    {
        temp->prev = NULL;
        head = tail = temp;
    }
}



int main()
{

    List list;
    int n, num;
        cout << "Enter N :  "; cin >> n;
        n = abs(n);
    int* simp = new int[2 * n]; 
    // eratosphene's sieve
    for (int i = 0; i < 2 * n; i++) {
        simp[i] = i;
    }
    simp[1] = 0;
    for (int l = 2; l < 2 * n; l++) {
        if (simp[l] != 0) {
            for (int j = l * 2; j < 2 * n; j += l) {
                simp[j] = 0;
            }
        }
    }
    for (int i = n; i < 2 * n; i++) {
        if (simp[i]) {
            num = simp[i];
            list.Add(num);
        }
    }
    cout << "Prime numbers of the list:\n";
    list.Print(); 
    return 0;
}

Answer 1

Давайте на мгновение оставим код в стороне и представим, что вы могли бы сделать это с помощью ручки и бумаги: вы должны были бы записать числа 2 3 4 ... 2n и начать с «2» (внешний l oop). Затем вы должны (внутренний l oop) отмечать (обратите внимание: НЕ стирать, а только отмечать!) Каждое второе число, начинающееся с 2 * 2 = 4. Затем вы должны вернуться к внешнему l oop, считать «3» и пометить каждое третье число, начинающееся с 3 * 2 = 6 (на самом деле, также можно начинать с 3 ^ 2 = 9).
Это маркировка переводится в установку элементов в массиве на 0, и в качестве последнего шага вы будете рассматривать только немаркированные (т.е. не 0) элементы.

В вашем подходе теперь вы хотите удалить узлы из связанного списка . Перевести это на язык ручки и бумаги - значит стереть числа с бумаги. Затем вы снова начинаете с «2», стираете кратные 2, затем go до «3» и стираете кратные 3. Важное изменение заключается в том, что вы больше не можете просто слепо стирать каждое третье число, но вы бы на самом деле нужно смотреть на числа и спрашивать себя: это кратное 3?

Конечно, вы могли бы это сделать, и вы также можете запрограммировать это, но это уже не будет решето для эратосфена. Сила алгоритма заключается в том, что любые кратные числа легко обнаруживаются по их индексу:
В предоставленном вами коде simp[i] == 0 || simp[i] == i сохраняется все время, т.е. число либо помечено, либо его индекс на самом деле является значением сам. Следовательно, вам не нужно смотреть на число и проверять, можно ли его разделить, вы можете просто сделать суждение на основе его индекса.

Answer 2

Нет, с вашей программой все в порядке, просто она потеряла некоторую эффективность сита эратосфенов . Проблема в вашем сите внутреннем l oop и внешнем l oop, должны выглядеть следующим образом.

// upper bound = sqrt(2 * n) rather than (2 * n)

// l < (2 * n) -----> [ l*l < 2 * n is same as l < sqrt(2 * n) ]
for (int l = 2; l*l < 2 * n; l++) {
    if (simp[l] != 0) {

        // lower bound = l * l rather than (2 * l)
        for (int j = l * l; j < 2 * n; j += l) {
            simp[j] = 0;
        }
    }
}

Для внутреннего l oop как (2*l) всегда меньше чем (l*l) за исключением случая 2 (2 * l) = (l * l), так что никакой разницы, просто бесполезно итераций .