Решето Эратосфена С#

• В данной работе представлены ТОЛЬКО ИСХОДНИКИ проекта C# Visual Studio 2010 WinForms
• Исходное задание на курсовую работу: Дано натуральное число n (n>=2). Найти все меньшие n простые числа, используя решето Эратосфена.

Анимация алгоритма.

Целое число, большее 1, называется простым, если оно не делится нацело ни на какое другое, кроме себя и 1.

Древний алгоритм «Решето Эратосфена» для поиска всех простых чисел до n выглядит так:

• Создать список последовательных чисел от 2 до n: 2, 3, 4, ..., n.
• Пусть p=2, это первое простое число.
• Зачеркнуть все последующие числа в списке с разницей в p, т.е. 2*p, 3*p, 4*p и т.д. В случае p=2 это будут4,6,8....
• Поменять значение p на первое не зачеркнутое число после p.
• Повторить шаги 3-4 пока p2 < n.
• Все оставшиеся не зачеркнутыми числа — простые.

Фрагмент программного кода
            //составляем список из чисел от 2 до n
            List<int> numbers = new List<int>();
            for (i = 2;i<=n;i++)
                numbers.Add(i);

            //для каждого числа
            for (i = 0; i<numbers.Count; i++)
            {
                //идем по остальным числам
                for (j=i; j<numbers.Count;j++)
                {
                    //вычеркиваем большие кратные числа
                    if ((numbers[i] != numbers[j]) && (numbers[j] % numbers[i] == 0))
                    {
                        numbers.RemoveAt(j);
                        j--;	
                    }
                }
            }

            richTextBox.AppendText("Простые числа:\n");
            String s = "";
            for (i=0; i<numbers.Count;i++)
                s += numbers[i].ToString() + " ";
            richTextBox.AppendText(s);

            //список хранения четерок
            List<int> four = new List<int>();
            //текущее число найденых чисел одного интервала и сам интервал
            int interval = 0;
            richTextBox.AppendText("\nЧетверки простых чисел:\n");

            for (i = 0; i<numbers.Count; i++)
            {
                //если первый или новый интервал сбрасываем значения
                if ((i == 0) || (numbers[i] / 10 != interval))
                {
                    interval = numbers[i] / 10;
                    four.Clear();
                }
                //если интервал не изменился записывем число
                if (numbers[i] / 10 == interval)
                {
                    four.Add(numbers[i]);

                    //если записано 4 числа выводим на экран
                    if (four.Count == 4)
                    {
                        s = "";
                        for (j = 0; j < 4; j++)
                            s += four[j].ToString() + " ";
                        richTextBox.AppendText(s+"\n");
                        
                    }
                }
            }

Содержание архива

• исходный код  на C# WinForms для Visual Studio