时间戳

首页 > 解决方案 > 使用单链表筛选 Eratosthenes C++

c++ - 使用单链表筛选 Eratosthenes C++

问题描述

嗨，我对 C++ 中的 Eratosthenes 筛有疑问。我必须使用单链表来做到这一点。我的程序正在运行并显示列表的第一个声明，但我不知道如何正确删除非素数。我的功能对我不起作用。我应该如何更改我的删除功能？

#include <iostream>
#include <cmath>

using namespace std;

struct List
{
    int number;
    List* next;
};
List* head = new List;
void l_add(int n)
{
    List* temp = head;
    for (int i = 2; i <= n; i++)
    {
        temp->next = new List();
        temp->number = i;
        temp = temp->next;
    }
}
void l_print()
{
    List* temp = head;
    while (temp->next != 0)
    {
        cout << temp->number << " ";
        temp = temp->next;
    }
    cout << endl;
}
void l_delete(int n)
{
    List* temp = head;
    for (int i = 2; i < sqrt(n); i++)
    {
        if (temp->number % i == 0)
        {
            head = temp->next;
            delete temp;
            temp = head;
        }
        while (temp->next != 0)
        {
            if (temp->next->number % i == 0)
            {
                temp->next = temp->next->next;
                delete temp->next;
            }
            temp = temp->next;
        }
    }
}
int main()
{
    int n;
    cout << "Enter up to which number to find prime numbers using Sieve of Eratosthenes: " << endl;
    cin >> n;
    l_add(n);
    l_print();
    l_delete(n);
    l_print();
    return 0;
}

标签： c++singly-linked-listsieve-of-eratosthenes

解决方案

这将是 l_delete 方法的工作版本：

void l_delete(int n)
{
    List* temp = head;
    for (int i = 2; i < sqrt(n); i++)
    {
        while (temp->next != 0)
        {
            if (temp->next->number % i == 0 && temp->next->number != i)
            {
                List* temp2 = temp->next->next;
                delete temp->next;
                temp->next = temp2;
            }
            if(temp->next == 0) break;
            temp = temp->next;
        }
        temp = head;
        if (temp->number % i == 0 && temp->number != i)
        {
            head = temp->next;
            delete temp;
            temp = head;
        }
    }
}

您的删除方法有几个问题。算法逻辑的问题：你的算法头应该最后检查，否则如果它被删除，新的头不会检查素数，你会立即检查新的下一个，它是旧的->下一个->下一个。此外，您没有检查数字是否等于分隔符，在这种情况下不应将其删除。

编程逻辑问题：当你在while循环中删除下一个节点时，与删除head时一样，你需要另一个临时变量来存储temp->next->next，然后在删除后将其分配给temp->next。

但这里最大的问题是，这根本不是 Eratosthenes 筛子，你只是在检查所有数字与所有其他小于 sqrt(n) 的数字的可分性。与 Eratosthenes 筛相比，它是次优的。如果你用谷歌搜索 Eratosthenes 筛子，你会发现很多详细的教程和解释。

推荐阅读