Алгоритм нахождения простых чисел
Оптимизация алгоритма нахождения простых чисел
Дело было давно, в университете, когда мы начали изучать язык программирования Pascal и домашним заданием стало создание алгоритма нахождения простых чисел.
Алгоритм был придуман и тутже реализован на изучаемом языке. Программа запрашивала у пользователя число N и искала все простые числа до N включительно. После первого успешного теста сразу же возникло непреодолимое желание ввести N = «много». Программа работала, но не так быстро как хотелось бы. Естественно, дело было в многочисленных проверках (порядка N*N/2), поэтому пришлось избавиться от лишних. В итоге получилось 5 похожих алгоритмов каждый из которых работал быстре предыдущего. Недавно захотелось их вспомнить и реализовать, но на этот раз на Python.
Итак, поехали. Первый алгоритм, ударивший в студенческую голову, продемонстрирован в Листинге 1.
Очень быстро понимаешь, что в подсчете делителей каждого числа нет никакой надобности и поэтому переменную k можно освободить от своих обязанностей. Действительно, если хотябы один делитель имеется, то число уже не простое. Смотрим Листинг 2.
Конструкция break позволяет нам завершить выполнение внутреннего цикла и перейти к следующей итерации внешнего.
Далее возникает вопрос: «а зачем делить на 4, если на 2 число не делится?». Приходим к выводу, что искать делители нужно только среди простых чисел не превышающих делимое. Наш алгоритм превращается в… см. Листинг 3.
А потом вспоминаем теорию чисел и понимаем, что переберать надо только числа, не превосходящие корня из искомого. К примеру, если число M имеет делитель pi, то имеется делитель qi, такой, что pi * qi = M. То есть, чтобы найти пару, достаточно найти меньшее. Среди всех пар, предполагаемая пара с максимальным наименьшим — это пара с равными pi и qi, то есть pi * pi = M => pi = sqrt(M). Смотрим Листинг 4.
Код из Листинга 4 при N=10000 выполняется примерно в 1000 раз быстрее, чем самый первый вариант. Есть еще один «ускоритель», проверять только те числа, которые заканчиваются на 1, 3, 7 или 9 (так как остальные очевидно делятся на 2 или 5). Наблюдаем Листинг 5.
В следствии незначительного изменения Листинга 5 получаем небольшую прибавку в скорости:
Итого: Программа из последнего листинга выполняется, примерно, в 1300 раз быстрее первоначального варианта.
Я не ставил перед собой задачи написать программу максимально быстро решающую данную задачу, это скорее демонстрация начинающим программистам того, что правильно составленный алгоритм играет далеко не последнюю роль в оптимизации Ваших программ.
P.S.
Благодаря замечаниям получаем Листинг 7:
при N=10000, поучаем время:
time 1 = 26.24
time 2 = 3.113
time 3 = 0.413
time 4 = 0.096
time 5 = 0.087
time 6 = 0.083
time 7 = 0.053
Результаты при n = 1 000 000:
time 7 = 7.088
time 8 = 1.143
22 полезных примера кода на Python
Python — один из самых популярных языков программирования, чрезвычайно полезный и в решении повседневных задач. В этой статье я вкратце расскажу о 22 полезных примерах кода, позволяющих воспользоваться мощью Python.
Некоторые из примеров вы могли уже видеть ранее, а другие будут новыми и интересными для вас. Все эти примеры легко запоминаются.
1. Получаем гласные
2. Первая буква в верхнем регистре
Этот пример используется для превращения каждой первой буквы символов строки в прописную букву. Он работает со строкой из одного или нескольких символов и будет полезен при анализе текста или записи данных в файл и т.п.
3. Печать строки N раз
Этот пример может печатать любую строку n раз без использования циклов Python.
4. Объединяем два словаря
Этот пример выполняет слияние двух словарей в один.
5. Вычисляем время выполнения
Этот пример полезен, когда вам нужно знать, сколько времени требуется для выполнения программы или функции.
6. Обмен значений между переменными
Это быстрый способ обменять местами две переменные без использования третьей.
7. Проверка дубликатов
Это самый быстрый способ проверки наличия повторяющихся значений в списке.
8. Фильтрация значений False
9. Размер в байтах
Этот пример возвращает длину строки в байтах, что удобно, когда вам нужно знать размер строковой переменной.
10. Занятая память
Пример позволяет получить объём памяти, используемой любой переменной в Python.
11. Анаграммы
Этот код полезен для проверки того, является ли строка анаграммой. Анаграмма — это слово, полученное перестановкой букв другого слова.
12. Сортировка списка
Этот пример сортирует список. Сортировка — это часто используемая задача, которую можно реализовать множеством строк кода с циклом, но можно ускорить свою работу при помощи встроенного метода сортировки.
13. Сортировка словаря
14. Получение последнего элемента списка
15. Преобразование разделённого запятыми списка в строку
Этот код преобразует разделённый запятыми список в единую строку. Его удобно использовать, когда нужно объединить весь список со строкой.
16. Проверка палиндромов
Этот пример показывает, как быстро проверить наличие палиндромов.
17. Перемешивание списка
18. Преобразование строки в нижний и верхний регистры
19. Форматирование строки
Этот код позволяет форматировать строку. Под форматированием в Python подразумевается присоединение к строке данных из переменных.
20. Поиск подстроки
Этот пример будет полезен для поиска подстроки в строке. Я реализую его двумя способами, позволяющими не писать много кода.
21. Печать в одной строке
Мы знаем, что функция print выполняет вывод в каждой строке, и если использовать две функции print, они выполнят печать в две строки. Этот пример покажет, как выполнять вывод в той же строке без перехода на новую.
22. Разбиение на фрагменты
Этот пример покажет, как разбить список на фрагменты и разделить его на меньшие части.
На правах рекламы
Серверы для разработчиков — выбор среди обширного списка предустановленных операционных систем, возможность использовать собственный ISO для установки ОС, огромный выбор тарифных планов и возможность создать собственную конфигурацию в пару кликов, активация любого сервера в течение минуты. Обязательно попробуйте!
Задача на Python, просьба помочь понять формулу, как она реализована?
Всем доброго времени суток. Уважаемые кодеры.
Я сейчас прохожу начальные курсы по пайтону и там была вот такая вот задачка:
В институте биоинформатики по офису передвигается робот. Недавно студенты из группы программистов написали для него программу, по которой робот, когда заходит в комнату, считает количество программистов в ней и произносит его вслух: «n программистов».
Для того, чтобы это звучало правильно, для каждого n нужно использовать верное окончание слова.
Напишите программу, считывающую с пользовательского ввода целое число n (неотрицательное), выводящее это число в консоль вместе с правильным образом изменённым словом «программист», для того, чтобы робот мог нормально общаться с людьми, например: 1 программист, 2 программиста, 5 программистов.
В комнате может быть очень много программистов. Проверьте, что ваша программа правильно обработает все случаи, как минимум до 1000 человек.
Дополнительный комментарий к условию:
Обратите внимание, что задача не так проста, как кажется на первый взгляд. Если ваше решение не проходит какой-то тест, это значит, что вы не рассмотрели какой-то из случаев входных данных (число программистов 0 ≤ n ≤ 1000). Обязательно проверяйте свои решения на дополнительных значениях, а не только на тех, что приведены в условии задания.
Я набросал код, все вроде как работало, но не проверил на числа 21, 31, 41 и т.п.
То есть мой код при вводе 21, выдавал вместо 21 программист, 21 программистов.
Также было и с числом допустим 994, мой код выдавал 994 программистов, вместо 994 программиста.
Все остальное работало. Один участник курсов, написал мне ответ, но не хочет объяснять как он вывел формулу правильного вычисления.
Формулу под номером 1 я понял, то есть если остаток числа n равен 1 и остаток не равен 11, то это программист.
Во второй формуле я понял только, что если остаток n больше или равен 2 и меньше или равен 4, то это программиста, а вот вторую часть формулы не как не могу понять.
Если кому не трудно уделить 5-10 минут времени, дайте пожалуйста внятное объяснение.
Python с абсолютного нуля. Учимся кодить без скучных книжек
Содержание статьи
От редакции
Недавно мы проводили опрос о том, какой курс по Python был бы интереснее читателям. Две первые строчки с большим отрывом в нем заняли варианты «для хакера» и «Python с нуля». Узнав о таком положении дел, мы немедленно заказали статью о том, как начать программировать на Python. Если она будет иметь успех, то может превратиться в целую серию. Отличие нашего подхода — в том, что мы объясняем все живым языком и даем нескучные примеры. В общем, обучение в фирменном стиле «Хакера»!
И, поскольку это эксперимент, статья доступна без платной подписки.
Если у тебя на компе есть современный дистрибутив Linux, то в него уже входит Python 3, а писать первые программы будет удобно в IDLE — простом редакторе кода, который прилагается к Python. В Ubuntu, чтобы установить его, набери в консоли
В Windows при установке Python обязательно отметь на первом экране установщика галочку Add to Path, чтобы можно было запускать python3 из командной строки в любом удобном месте.
Запустив IDLE, зайди в Options → Configure IDLE, перейди на вкладку General и поставь галочку на пункте Open Edit Window, нажми ОK и перезапусти IDLE. Теперь можно писать программы, сохранять их и запускать клавишей F5. Ну что, погнали?
Переменные
А если изначально неизвестно, какие числа надо складывать? Тогда пришлось бы сперва попросить юзера ввести их в консоли и нажать Enter. Давай так и сделаем:
Внутри скобочек у input ты пишешь пояснение для юзера, что конкретно его просят ввести. Но вот беда, по умолчанию все, что вводится через input, считается не числом, а строкой, поэтому, прежде чем складывать количество литров пива, нужно сначала преобразовать введенные строки в числа с помощью функции int().
Вообще, типов переменных много, но суть ты уловил — чтобы производить с переменными какие‑то действия, нужно их сначала привести к одному типу — к строковому, или к числовому, или еще к какому‑нибудь. Если с этим не заморачиваться, Python сложит не числа, а строки и введенные 2 и 3 литра пива в сумме дадут не 5, а целых 23. Хорошо бы так было в реальности!
Вот еще примерчик, рассчитывающий, сколько тебе еще пить пиво, исходя из средней продолжительности жизни в России:
Условия
В основе любой программы лежат условия. В зависимости от того, выполняются они или не выполняются, программа может пойти по одному или другому пути. Представь, ты едешь на машине и смотришь на часы: если уже есть десять вечера, то поворачиваешь домой, если нет, то можно заехать в гости. Точно так же работает и программа: проверяет какое‑то значение и сворачивает туда или сюда и выполняет соответствующий кусочек кода.
Блоки кода в Python отделаются отступами. Отступ на самом деле может быть любым, например некоторые предпочитают использовать вместо четырех пробелов клавишу Tab. Главное — не смешивать в одной программе отступы разного типа. Если уж начал использовать четыре пробела, то используй по всей программе, а то Python будет на тебя ругаться и унижать.
Еще один важный момент здесь — это знак равенства в условии. Он пишется как двойное «равно» ( == ) и этим отличается от присвоения — одинарного «равно».
Функция lower(), прежде чем сравнивать условие, делает все буквы в строке маленькими, потому что глупый юзер может ввести слово YES с горящим Caps Lock, и это надо предусмотреть заранее.
На самом деле lower( ) — не просто функция, а метод класса string (строка). Именно поэтому он вызывается через точку после переменной, которая содержит строку. О классах и методах мы поговорим как‑нибудь в другой раз, а пока просто запомни, что некоторые функции вызываются таким образом.
Пример простой программы на Python – пишем с нуля
В этом разделе мы обсудим основной синтаксис и разберем пример Python – запустим простую программу для печати Hello World на консоли.
Python предоставляет нам два способа запуска программы:
Давайте подробно обсудим каждый из них.
Интерактивная подсказка помощника
Python предоставляет нам возможность выполнять инструкции интерактивного помощника. Это предпочтительнее в том случае, когда нас беспокоит вывод каждой строки программы Python.
Чтобы использовать интерактивный режим, откройте терминал(или командную строку) и введите python(python3 в случае, если в вашей системе установлены Python2 и Python3).
Откроется следующее приглашение, в котором мы можем выполнить оператор Python и проверить влияние на консоль.
После написания отчета о печати нажмите клавишу Enter.
Здесь мы получаем сообщение “Hello World!” на консоли.
Использование файла сценария(Программирование в режиме сценария)
Подсказка интерпретатора лучше всего подходит для выполнения однострочных операторов кода. Однако мы не можем писать код каждый раз на терминале. Не рекомендуется писать несколько строк кода.
Чтобы запустить этот файл с именем first.py, нам нужно запустить следующую команду на терминале.
Шаг – 1: Откройте интерактивную оболочку Python и нажмите «Файл», затем выберите «Создать», откроется новый пустой скрипт, в котором мы можем написать наш код.
Шаг 2: Теперь напишите код и нажмите «Ctrl + S», чтобы сохранить файл.
Шаг – 3: После сохранения кода мы можем запустить его, нажав «Выполнить» или «Выполнить модуль». Он отобразит вывод в оболочку.
Результат будет показан следующим образом.
Шаг – 4: Кроме того, мы также можем запустить файл с помощью терминала операционной системы. Но мы должны знать путь к каталогу, в котором мы сохранили наш файл.
Многострочные операторы
Плюсы и минусы режима сценария
Режим сценария также имеет несколько преимуществ и недостатков. Давайте разберемся в следующих преимуществах запуска кода в режиме скрипта:
Посмотрим на недостатки скриптового режима:
Начало работы с PyCharm
В нашей первой программе мы использовали gedit в CentOS в качестве редактора. В Windows у нас есть альтернатива, например блокнот или блокнот ++, для редактирования кода. Однако эти редакторы не используются в качестве IDE для Python, поскольку они не могут отображать предложения, связанные с синтаксисом.
JetBrains предоставляет самую популярную и широко используемую кроссплатформенную IDE PyCharm для запуска программ Python.
Установка PyCharm
Как мы уже говорили, PyCharm – это кроссплатформенная IDE, поэтому ее можно установить в различных операционных системах. В этом разделе руководства мы рассмотрим процесс установки PyCharm в Windows, MacOS, CentOS и Ubuntu.
Windows
Установить PyCharm в Windows очень просто. Чтобы установить PyCharm в операционной системе Windows, перейдите по ссылке https://www.jetbrains.com/pycharm/download/download-thanks.html?platform=windows, чтобы загрузить установщика. Дважды щелкните файл установки(.exe) и установите PyCharm, нажимая «Далее» на каждом шаге.
Чтобы создать первую программу для Pycharm, выполните следующий шаг.
Шаг – 1. Откройте редактор Pycharm. Нажмите на «Создать новый проект», чтобы создать новый проект.
Шаг – 2. Выберите место для сохранения проекта.
Шаг – 3. Щелкните меню «Файл» и выберите «Новый». При нажатии на опцию «Новый» он покажет различные форматы файлов. Выберите «Файл Python».
Шаг – 4. Теперь введите имя файла Python и нажмите «ОК». Мы написали «Первую программу».
Шаг – 5. Теперь введите первую программу – print(«Hello World»), затем нажмите меню «Выполнить», чтобы запустить программу.
Шаг – 6. Результат появится внизу экрана.
Базовый синтаксис Python
Отступы в Python
Отступы – наиболее важная концепция языка программирования Python. Неправильное использование отступов приведет к ошибке “IndentationError” в нашем коде.
Отступы – это не что иное, как добавление пробелов перед оператором, когда это необходимо. Без отступа Python не знает, какой оператор выполнять следующим. Отступ также определяет, какие операторы принадлежат какому блоку. Если нет отступа или отступ неправильный, отобразится «IndentationError» и прервет наш код.
Отступы Python определяют, какая группа операторов принадлежит конкретному блоку. В языках программирования, таких как C, C ++, java, для определения блоков кода используются фигурные скобки <>.
В Python операторы, находящиеся на одном уровне справа, принадлежат одному блоку. Мы можем использовать четыре пробела для определения отступа. Давайте посмотрим на следующие строки кода.
В приведенном выше коде цикл for имеет блоки кода, если оператор имеет блок кода внутри цикла for. Оба с четырьмя пробелами с отступом. Последний оператор print() без отступа; это означает, что он не принадлежит циклу for.
Комментарии в Python
Комментарии необходимы для определения кода и помогают нам и другим людям понять код. Просматривая комментарий, мы можем легко понять назначение каждой строки, написанной нами в коде. Мы также можем очень легко найти ошибки, исправить их и использовать в других приложениях.
В Python мы можем применять комментарии, используя символ решетки #. Интерпретатор Python полностью игнорирует строки, за которыми следует символ решетки. Хороший программист всегда использует комментарии, чтобы сделать код стабильным. Давайте посмотрим на следующий пример комментария.
Мы можем добавить комментарий в каждую строку кода Python.
Хорошая идея – добавить код в любую строку раздела кода, цель которого неочевидна. Это лучший способ изучить при написании кода.
Типы комментариев
Python предоставляет возможность писать комментарии двумя способами – однострочный комментарий и многострочный комментарий.
Однострочный комментарий начинается с символа решетки #, за которым следует текст для дальнейшего объяснения.
Мы также можем написать комментарий рядом с оператором кода. Рассмотрим следующий пример.
Многострочные комментарии – Python не имеет явной поддержки многострочных комментариев, но мы можем использовать символ решетки # для нескольких строк. Например –
Мы также можем использовать другой способ.
Это основное введение в комментарии. Просмотрите наш урок по комментариям Python, чтобы изучить его подробно.
Идентификаторы Python
Идентификаторы Python относятся к имени, используемому для идентификации переменной, функции, модуля, класса, модуля или других объектов. Есть несколько правил, которым нужно следовать при присвоении имени переменной Python.
Мы определили базовый синтаксис языка программирования Python. Мы должны ознакомиться с основной концепцией любого языка программирования. Как только мы запомним концепции, упомянутые выше, изучение Python станет проще.