Sito Eratostenesa

Tablicowa wersja sita Eratostenesa

#include<iostream>
#include<cstdlib>

using namespace std;

int main(int argc,char **argv)
{
    long int counter,i,j,n;
    bool *p;
    n = atol(argv[1]);
    p = new bool[n+1];
    p[0] = false;
    p[1] = false;
    counter = 0;
    for(i = 2;i <= n;i++)
        p[i]=true;
    i = 2;
    while(i <= n)
    {
        if(p[i])
        {
            j = i + i;
            while(j <= n)
            {
                p[j] = false;
                j+=i;
            }
        }
        i++;
    }
    for(i = 2; i <= n;i++)
        if(p[i])
        {
            cout << i << " -> ";
            counter++;
        }
        cout << '\n';
        cout << " Liczba liczb pierwszych :" << counter <<"\n";
    delete[] p;
    return 0;
}


Listowa wersja sita Eratostenesa

#include<iostream>
#include<cstdlib>

using namespace std;

typedef long int TData;

struct node
{
    TData data;
    struct node *next;
};

typedef struct node node;

void ListInit(node *&head)
{
    head = nullptr;
}

bool ListIsEmpty(node *head)
{
    return head == nullptr;
}

void ListPrint(node *head)
{
    node *p = head;
    long int counter = 0;
    while(p != nullptr)
    {
        cout << p->data << " -> ";
        counter++;
        p = p->next;
    }
    cout<<"NULL \n";
    cout<<"Liczba wezlow listy : "<< counter<<"\n";
}

node *ListSearchNode(node *head,TData k,node *&prev)
{
    node *curr = head;
    prev = nullptr;
    while(curr != nullptr && curr->data != k)
    {
        prev = curr;
        curr = curr->next;
    }
    return curr;
}

void ListPush(node *&head,TData k)
{
    node *x = new node;
    x->data = k;
    x->next = head;
    head = x;
}

void ListPop(node *&head)
{
    node *x;
    if(!ListIsEmpty(head))
    {
        x = head;
        head = x->next;
        delete x;
    }
}

void ListDeleteNode(node *&head,TData k)
{
    node *x,*y;
    x = ListSearchNode(head,k,y);
    if(x != nullptr)
    {
        if(head == x)
            head = x->next;
        else
            y->next = x->next;
        delete x;
    }
}

int main(int argc, char**argv)
{
    long int j,n;
    node *aux;
    node *head;
    ListInit(head);
    n=atol(argv[1]);
    for(j = n;j>=2;j--)
        ListPush(head,j);
    aux = head;
    while(aux != nullptr)
    {
        j = aux->data+aux->data;
        while(j <= n)
        {
            ListDeleteNode(head,j);
            j+=aux->data;
        }
        aux = aux->next;
    }
    ListPrint(head);
    while(!ListIsEmpty(head))
        ListPop(head);
    return 0;
}