Главная · Карта сайта · Поиск · Статьи · Компьютерные курсы · Обучающие программы · Открытые проекты · Веб-программирование · Создание интернет-сайта · Полезные ссылки · Глоссарий · Контакты · Декабрь 09 2016 22:15:14
Последнее опубликованное

Что такое Model-View-Controller
Pattern Model-View-Controller

Как создать свой веб-сайт
Как создать свой сайт в интернете

Разное
Статистика

Основы программирования. Простые числа


Содержание курса

Граница между простым и сложным...

Шаг 2. Нахождение простых чисел

Простое число – это такое натуральное число, которое делится только на единицу и на само себя. Вот поиском таких чисел мы и займемся. Сразу скажу, что существует достаточно много предложений, как оптимизировать поиск простых чисел – это весьма интересная и занимательная задача. Вот одно из самых древних решений – решето Эратосфена. Быстрый поиск простых чисел может оказаться весьма сложным занятием, поэтому мы займемся поиском простых чисел, что называется, “в лоб” - методом перебора всех вариантов от 2 до определенного пользователем максимального числа. Не вводите в тестовых программах слишком большое максимальное число, иначе, вы рискуете загрузить ваши вычислительные мощности на максимум и надолго.

Описание алгоритма

Мы будем проверять каждое число на деление его без остатка на числа из последовательности от 2 до целой части от квадратного корня исходного числа. Например, для числа 17 это будут числа 2,3,4. Понятно, что после неудачной проверки деления на 2 проверять деление на остальные четные числа смысла не имеет, но про эту оптимизацию чуть позже. Если остаток от деления будет равен нулю, то это означает, что число не простое, и мы завершаем проверку.

Используемые конструкции языка программирования

Процедура или функция – отдельная поименованная часть программы. Группировку программного кода по процедурам и функциям используют для выделения повторяющейся функциональности, выполняющей законченные с точки зрения контекста вызова действия, например ввод и вывод данных, математические расчеты, разного рода проверки и т.п. Функции и процедуры могут иметь аргументы – входные параметры, значения которых определяются по месту их вызова. Для функции, в отличие от процедуры также должно быть определено значение результата, которое можно использовать в операторах присваивания, математических выражениях и логических условиях путем подстановки вызова функции в качестве аргумента перечисленных операций.

Фрагмент исходного кода

Присвоение значения вызову функции на обоих представленных языках программирования выполняется с использованием ключевого слова return. Функция IsPrime является логической (булевой), и для нее определено всего два варианта исхода: return true (ИСТИНА), если число простое и return false (ЛОЖЬ), если нет. Исходный код функции проверки: является ли число простым на языках программирования C# и VB.NET представлен ниже:

C#:
    static bool IsPrime(int d)
    {
        //Приведение вещественного результата к целочисленному типу (int) с потерей точности
        int _sqrt_int = (int)Math.Sqrt(d); //Целая часть от квадратного корня из d

        for (int i = 2; i <= _sqrt_int; i++)
            if ((d % i) == 0) //Проверка: остаток от деления d/i==0?
                return false;

        return true;
    }
VB.NET:
Shared Function IsPrime(ByVal d As Integer) As Boolean
    'Приведение вещественного результата к целочисленному типу CType(Double, Integer) с потерей точности
    Dim _sqrt_int As Integer = CType(Math.Sqrt(d), Integer)

    For i As Integer = 2 To _sqrt_int
        If (d Mod i) = 0 Then
            Return False
        End If
    Next

    Return True
End Function

Полные версии алгоритмов

На языке C#.
На языке VB.NET.

Оптимизация алгоритма поиска простых чисел методом перебора

Приведенные алгоритмы нужно оптимизировать: отдельно проводить проверку деления на 2, и если число на два не делится, то продолжать проверку деления от 3 до целой части от квадратного корня числа с шагом 2!. Для того чтобы цикл осуществлял проверку с шагом 2, в процедуре IsPrime, в определении цикла for нужно внести следующие изменения: в алгоритме на C# нужно i++ заменить на i+=2, а в алгоритме на VB.NET добавить инструкцию Step 2. Естественно, что сам цикл должен в этом случае начинаться уже с 3, а перед ним должна быть отдельно добавлена проверка деление на 2. Попробуйте самостоятельно оптимизировать эти алгоритмы. Для проверки их корректности сравнивайте результаты с приведенной последовательностью:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, …

Если не получится, то скачайте исправленные версии по ссылкам ниже.

Исправленные (оптимизированные) версии алгоритмов

На языке C#.
На языке VB.NET.

Резюме

Просмотрев код этих алгоритмов, на примере функции IsPrime вы познакомитесь с приемом выделения отдельных фрагментов кода в процедуры или функции с параметрами. С циклом for и оператором условного перехода if вы уже знакомы по алгоритму сортировки чисел методом “пузырька”.

Далее: Рекурсивное вычисление факториала.



Компьютерные курсы и курсы программирования
Основы программирования

Курс для начинающих программистов на C# и VB.NET.

SQL 25™

Построение SQL запросов и работа с базой данных.

C# Quick Guide™

Программирование на C#. Краткое руководство.

RegEx

Применение регулярных выражений.

Plug-in архитектура

Примеры программной Plug-in архитектуры.

XML и его расширения

Язык разметки XML и его расширения с примерами.

HTML и разметка гипертекста

Языки HTML, XHTML и CSS с примерами разметки.

Основы веб-дизайна

Основы веб-дизайна: решения типовых задач верстки.

Программирование на PHP

Руководство по программированию на PHP для начинающих.

Справочные материалы

Шаблоны проектирования
Каталог шаблонов проектирования программных компонентов.

Рефакторинг кода
Каталог приемов рефакторинга программного кода.

Гость
Имя

Пароль



Забыли пароль?
Запросите новый здесь
.
Coding Craft. Все права защищены © 2011. Проект Инициативного Народного Фронта Образования - ИНФО-проект.