UnKnownHeIp

Доброго времени суток, товарищи! Сегодня мы коснемся такой темы, как факторизация числа - разложение числа на простые множители. Существование и единственность такого разложения следует из основной теоремы арифметики. Сегодня мы поверхностно пройдемся по теме, разберем простейшим алгоритм, достаточный для олимпиад, а в следующих статьях углубимся в тему и посмотрим алгоритмы Полларда, Бента, Монте-Карло и Ферма. Как мы знаем из предыдущих статей - делители числа будут только лишь до корня из этого числа (делители ходят парами)...

Доброго времени суток, товарищи! Сегодня будет заключающая статья про Решето Эратосфена, мы разберем оптимизацию решета - блочное решето. Напомню, что в прошлые разы мы посмотрели обычное решето и линрешето. Как мы знаем из одной из оптимизаций стандартного решета после корня из n невычеркнутыми останутся только простые числа, то есть просеивать нам достаточно лишь простыми до корня. Исходя из этого соображения мы можем до корня из n построить обычное решето и найти те числа, которыми мы будем вычеркивать,...

Доброго времени суток, товарищи! Сегодня речь пойдет в продолжение предыдущей темы, а именно, мы будем писать Решето Эратосфена за линию. Те, кто не знаком с оригинальным решетом - сюды. Основная проблема Эратосфена в том, что мы помечаем составные числа по несколько раз, наша задача состоит в том, чтобы как-то помечать числа только по разу. Предположим, что мы знаем минимальный простой делитель какого-то произвольного числа, k - p[k]. и, если мы будем домножать k на простые числа до p[k] (p[j]), то мы однозначно получим число, у которого наименьший простой делитель p[j]...

Доброго времени суток, товарищи! Сегодня я продолжу речь про простые числа, а именно, расскажу про Решето Эратосфена. Когда-то давным-давно древнегреческому математику Эратосфену Киренскому пришла в голову одна замечательная идея, который мы пользуемся и по сей день. Суть состоит в том, чтобы находить все простые числа до какого-то заданного n, вычеркиванием составных чисел. *составное число - число, которое можно представить в виде с = a*b, где ни a ни b не являются 1* Представим, что мы уже знаем, что 2 (первое простое число) - простое число...

Доброго времени суток, товарищи! Сегодня мне бы хотелось начать мой канал с довольно простой темы. На канале я собираюсь разбирать разные алгоритмы программирования, стараясь давать их лаконичным и простым языком, по этому же соображению писать я буду на python. Весь код статьи будет прикреплен на github. Ну что ж, давайте приступать! Простое число - число, которое из делителей имеет только 1 и само себя(например: 2, делится без остатка только на 1 и на 2), грубо говоря ни на что не делится. Стоит уточнить, что 1 простым числом не считается...