Найти простые числа используя решето Эратосфена и однонаправленный список - 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);
}
}