Найти простые числа используя решето Эратосфена и однонаправленный список - C#

Узнай цену своей работы

Формулировка задачи:

Дано натуральное число n (n≥2). Найти все меньшие n простые числа, используя решето Эратосфена. Решетом Эратосфена называют следующий способ. Выпишем подряд все целые числа от 2 до n. Первое простое число 2. Подчеркнем его, а все большие числа, кратные 2, зачеркнем. Первое из оставшихся чисел 3. Подчеркнем его как простое, а все большие числа, кратные, 3, зачеркнем. Первое число из оставшихся теперь 5, так как 4 уже зачеркнуто. Подчеркнем его как простое, а все большие числа, кратные 5 зачеркнем и т.д.:2, 3, 4,5, 6,7, 8, 9, 10, ... Исходную последовательность чисел организовать в виде однонаправленного списка. Удаление производить внутри этого списка, не используя дополнительные списки. Администрация и модераторы не удаляйте эту Тема пожалуйста, да на нее ответили, но не правильно! Помогите пожалуйста написать программу не на Basic, а на C# ибо показывал код преподу она сказала что он на Basic, а надо было на c#. Заранее спасибо

Решение задачи: «Найти простые числа используя решето Эратосфена и однонаправленный список»

textual
Листинг программы
class Node<T>
{
    public Node<T> Next;
    public T Value;
}
 
class SingleLinkedList<T>: IEnumerable<T>
{
    public class Iterator: IEnumerator<T>
    {
        private Node<T> _node;
        private SingleLinkedList<T> _list;
        
        public Iterator(SingleLinkedList<T> list)
        {
            _list = list;
        }
        
        public bool MoveNext()
        {
            if (_node == null)
            {
                _node = _list.Head;
            }
            else
            {
                _node = _node.Next;
            }
            
            return _node != null;
        }
        
        public void Reset()
        {
            _node = null;
        }
 
        public void Dispose() { _node = null; }
        
        public T Current => _node.Value;
        
        object IEnumerator.Current => Current;
    }
    
    public IEnumerator<T> GetEnumerator()
    {
        return new Iterator(this);
    }
    
    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
    
    private Node<T> _head;
    private Node<T> _tail;
 
    public Node<T> Head => _head;
 
    public void PushBack(T value)
    {
        var node = new Node<T> { Value = value };
        
        if (_tail == null)
        {
            _head = _tail = node;
            return;
        }
 
        _tail.Next = new Node<T> { Value = value };
        _tail = _tail.Next;
    }
    
    public void Remove(Node<T> node)
    {
        if (node == _head)
        {
            if (node == _tail)
            {
                _head = _tail = null;
            }
            else
            {
                _head = _head.Next;
            }
            return;
        }
 
        var curr = _head;
        while (curr.Next != node)
        {
            curr = curr.Next;
        }
 
        curr.Next = node.Next;
        if (_tail == node)
        {
            _tail = curr;
        }
    }
}
 
void ApplyEratosthenesSieveIteration(SingleLinkedList<int> list, Node<int> start)
{
    var curr = start;
    var prime = start.Value;
    
    while (curr != null)
    {
        var next = curr.Next;
        if (curr.Value > prime && curr.Value % prime == 0)
        {
            list.Remove(curr);
        }
        curr = next;
    }
}
 
void ApplyEratosthenesSieve(SingleLinkedList<int> list)
{
    var start = list.Head;
    while (start != null)
    {
        ApplyEratosthenesSieveIteration(list, start);
        start = start.Next;
    }
}
 
void Main()
{
    var list = new SingleLinkedList<int>();
    for (int i = 2; i < 100; i++)
    {
        list.PushBack(i);
    }
    
    ApplyEratosthenesSieve(list);
 
    foreach (var e in list)
    {
        Console.WriteLine(e);
    }
}

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

11   голосов , оценка 3.909 из 5
Похожие ответы