Привет, дорогой читатель. Даже если ты очень далек от программирования, дай этой статье шанс. Я ни разу не напишу определение слова "оптимизация кода", но ты все равно поймешь, что это такое. Я приведу примеры кода на языке питон, и ты поймешь каждую строчку. Ты ведь давно хотел понять, как пишут код! Это твой шанс не потратить ни одного джоуля энергии и разобраться в проблемах программирования. И даже с тем, как они решаются.
Давай напишем код, который будет выводить все простые числа на экран.
Сначала мы добьемся того, чтобы это просто работало. Затем ускорим наш код в несколько раз.
Итак, что такое простое число? Как нам его закодить?
Не зазорно залезть в гугл. Мы тут программисты, а не математики.
Просто́е число́ — натуральное число, имеющее ровно два различных натуральных делителя. Другими словами, натуральное число p является простым, если оно отлично от 1 и делится без остатка только на 1 и на само p
Спасибо, википедия! Кароч, простое число делится только на себя и на единицу. Сама единица простым числом не является. Это все, что нам нужно знать. Мы готовы писать код.
Идея кода
Мы переберем все натуральные числа от 2 до 100 и будем печатать его на экране, если оно не разделится ни на одно число от 2 до самого себя (не включительно), потому что на 1 и на само себя оно точно разделится.
Первая строчка:
Для каждого числа, которое претендует быть простым, нам нужно попытаться разделить его на все числа от 2 до самого себя. Ровно, как мы и планировали. Эта строчка будет почти такой же.
Например, для num=6 мы перереберем потенциальные делители 2, 3, 4 и 5.
Число 6 разделится на двойку и тройку из этого списка. Мы проверим это остатком от деления num на dels. Вот так:
А что тогда, кстати?
Если бы мы искали составные числа, то число 6 можно было бы сразу печатать на экране, так как оно имеет делители и мы это доказали. Но мы-то ищем простые числа.
Надо что-то придумать!
Напомню, к этому моменту наш код выглядит так:
Давайте рассуждать логически: если мы нашли один из делителей испытуемого num, значит оно точно не является простым, так?
Предлагаю завести для каждого числа num статус "простое", который оно может потерять, если мы найдем у него хотя бы один делитель.
Но если после перебора всех потенциальных делителей dels оно ни разу ни на что не разделится, то оно сохранит этот статус "простое".
Теперь нам понятно, что писать после третьей строчки.
Теперь наш код выглядит так:
Для кажого num мы авансом даем статус "простое". Но сразу после этого мы проводим проверку, не ошиблись ли мы с таким громким высказыванием.
Например, для того же числа 6, сначала мы объявим его простым. Потом попробуем разделить на 2, 3, 4 и 5. Шестерка, не будь дурой, разделится на 2 и 3. И дважды потеряет статус простого числа.
Супер! Нам осталось дописать всего 2 строки кода. В которых если num после проверки сохранит свой статус простого числа, то его можно выставлять в наш музей простых чисел.
Это будет выглядеть так:
Давайте насладимся его работой!
Ура! Мы молодцы и наш код — говно
Эй, Никита, я не успел порадоваться своей первой победе в программировании. Почему говно-то?
А потому что его можно сделать раз в 1000 более быстрым. Если мы будем искать все простые числа до 1 000 000 000, то он будет выполняться...
Честно, мне стало лень проверять, сколько он будет выполняться после 20 минут на секундомере. И это на топовом-то железе!
Очевидно, хороший код должен выдать ответ через несколько секунд.
Для этого нам нужно его оптимизировать!
Например, зачем продолжать искать делители, если один мы уже нашли?
А значит число точно составное и можно переходить к следующему.
Зачем мы ищем делители в промежутке от num/2 до num? Ведь если мы не встретили у числа 1 000 003 делителей в первой половине миллиона, то какой смысл проверять делители во второй? А есть оптимизационные приколы на несколько порядков круче.
Надеюсь, вы рады, что мы написали этот код, и не сильно расстроены, что он — говно. Теперь, как я и обещал, вы поняли, что такое оптимизация, и мы займемся ей в следующей статье!
Подпишись, чтобы мы не потерялись в информационном океане и напиши коммент в поддержку моего творчества <3
Спасибо, что прочли! Если вам понравилась бытовая информатика, то знайте, что я веду подготовку к ЕГЭ по информатике и ютюб-канал «Пацанская информатика», там тоже хорошо.