Напишите программу, которая перебирает целые числа, большие 1 481 011, в порядке возрастания и ищет среди них представленные в виде произведения ровно двух простых множителей, не обязательно…
- 1
Перебираем простые числа и оставляем только те, в десятичной записи которых ровно одна цифра 7.
- 2
Проверяем произведения пар подходящих простых множителей, начиная с чисел, больших 1 481 011.$$1117 \cdot 1327 = 1482259$$
Ещё 1 шаг — в полном решении
Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы: символ «?» означает ровно одну произвольную цифру; символ «*» означает любую последовательность…
- 1
Число с маской 1*23?9 имеет вид $A \cdot 10000 + 2309 + 10d$, где $d$ — последняя неизвестная цифра, а $A$ начинается с цифры 1.
- 2
Так как число не превышает $10^8$, длина последовательности вместо «*» может быть от 0 до 3 цифр. Для каждого варианта перебираем $d$ от 0 до 9 и проверяем делимость на 2023.
Ещё 3 шага — в полном решении
Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы: символ «?» означает ровно одну произвольную цифру; символ «*» означает любую последовательность…
- 1
Так как число не превышает $10^{10}$, в маске 89*6?7?9? символ «*» может задавать от нуля до двух цифр.
- 2
Перебираем все числа, кратные 9874, в диапазоне от минимального числа, соответствующего маске, до $10^{10}$.
Ещё 1 шаг — в полном решении
Пусть $R$ — сумма различных натуральных делителей целого числа, не считая единицы и самого числа. Напишите программу, которая перебирает целые числа, большие $500\,000$, в порядке возрастания и ищет…
- 1
Перебираем числа $n$, начиная с $500001$, в порядке возрастания.$$n=500001,500002,\ldots$$
- 2
Для каждого $n$ перебираем делители $d$ от 2 до $\lfloor\sqrt n\rfloor$. При обнаружении делителя добавляем к сумме $d$ и парный делитель $n/d$, если они различны и не равны самому числу.$$R(n)=\sum_{d\mid n,\ 1<d<n}d$$
Ещё 1 шаг — в полном решении
Пусть $M$ — сумма минимального и максимального простых натуральных делителей целого числа, не считая самого числа. Если таких делителей у числа нет, то значение $M$ считается равным нулю. Напишите…
- 1
Последовательно перебираем целые числа, большие $5\,700\,000$, и для каждого определяем минимальный и максимальный простые делители, не считая самого числа.
- 2
Для каждого числа вычисляем $M$ как сумму найденных делителей и проверяем условия $M > 70\,000$ и $M = k^2$ для некоторого натурального $k$.$$M=p_{\min}+p_{\max}=k^2$$
Ещё 1 шаг — в полном решении
Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы: символ «?» означает ровно одну произвольную цифру; символ «*» означает любую последовательность…
- 1
Так как число начинается с цифры 3 и не превышает $10^8$, длина последовательности, задаваемой символом «*», может быть от 0 до 2 цифр.
- 2
Перебираем цифры вместо «?» и последовательности цифр вместо «*», проверяя соответствие маске и делимость на 3023.
Ещё 1 шаг — в полном решении
Пусть $M$ — сумма минимального и максимального натуральных делителей целого числа, не считая единицы и самого числа. Если таких делителей у числа нет, то считаем значение $M$ равным нулю. Напишите…
- 1
Для каждого целого числа, начиная с $452022$, перебираем возможные делители до квадратного корня числа.$$1 < d \leq \sqrt{n}$$
- 2
Для составного числа минимальным нетривиальным делителем является первый найденный делитель $d$, а максимальным — парный делитель $n / d$. Поэтому $M = d + n/d$.
Ещё 2 шага — в полном решении
Напишите программу, которая перебирает целые числа, большие 2018974447, в порядке возрастания и ищет среди них числа, представленные в виде произведения ровно двух простых множителей, не обязательно…
- 1
Сформируем простые числа, в десятичной записи которых последовательность 43 встречается ровно один раз.
- 2
Для каждой пары таких простых чисел вычислим произведение и оставим произведения, превышающие 2018974447.$$n=p\cdot q>2018974447$$
Ещё 1 шаг — в полном решении
29ФИПИ 703256№ 25Повышенная Напишите программу, которая перебирает целые числа, бо́льшие 500 000, в порядке возрастания и ищет среди них такие, у которых есть натуральный делитель, оканчивающийся на цифру 9 и не равный ни…
- 1
Перебираем числа, начиная с 500001, и для каждого проверяем делители от 2 до квадратного корня из числа. Подходящими считаем делители, меньшие самого числа, не равные 9 и оканчивающиеся цифрой 9.
- 2
Первое найденное число — 500004: оно делится на 19, а 19 — минимальный подходящий делитель.
Ещё 1 шаг — в полном решении
Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы: символ «?» означает ровно одну произвольную цифру; символ «*» означает любую последовательность…
- 1
Маска без цифр вместо «*» задаёт семизначные числа вида $12ab156$. Проверка всех значений $a$ и $b$ даёт одно подходящее число.$$12206156 = 317 \cdot 3868$$
- 2
Если вместо «*» поставить одну цифру $c$, получаются восьмизначные числа вида $12ab1c56$. Перебор цифр $a$, $b$ и $c$ с проверкой делимости даёт три числа.$$12511356 = 317 \cdot 39468$$
Ещё 1 шаг — в полном решении
Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы: символ «?» означает ровно одну произвольную цифру; символ «*» означает любую последовательность…
- 1
Числа, кратные 1927 и не превышающие $10^8$, имеют вид $1927k$, где $1 \leq k \leq 51892$.$$k \leq \left\lfloor \dfrac{10^8}{1927} \right\rfloor = 51892$$
- 2
Для каждого значения $k$ вычисляется число $N=1927k$. Затем проверяется, что запись числа соответствует маске 1?3*4?9.
Ещё 1 шаг — в полном решении
Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы: символ «?» означает ровно одну произвольную цифру; символ «*» означает любую последовательность…
- 1
Так как число не превышает $10^8$, после префикса 1234 и суффикса 54 может находиться не более двух цифр.
- 2
При пустой последовательности получается число $123454$, которое не делится на 21.
Ещё 3 шага — в полном решении
Напишите программу, которая перебирает целые числа, большие 2 920 573, в порядке возрастания и ищет среди них числа, представленные в виде произведения ровно двух простых множителей, не обязательно…
- 1
Находим простые числа, в записи которых ровно одна цифра 9, и перебираем их произведения, начиная с чисел, больших 2 920 573.
- 2
Первое подходящее произведение — квадрат простого числа 1709.$$1709\cdot1709=2920681$$
Ещё 4 шага — в полном решении
Пусть $M$ — сумма минимального и максимального натуральных делителей целого числа, не считая единицы и самого числа. Если таких делителей у числа нет, то считаем значение $M$ равным нулю. Напишите…
- 1
Для каждого числа $n$ ищем его наименьший делитель $p$, больший единицы. Если делителей, кроме 1 и самого числа, нет, значение $M$ равно нулю.$$M = 0$$
- 2
Если $p$ найден, то максимальный собственный делитель числа равен $n/p$, поэтому вычисляем значение $M$.$$M = p + \dfrac{n}{p}$$
Ещё 1 шаг — в полном решении
Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы: символ «?» означает ровно одну произвольную цифру; символ «*» означает любую последовательность…
- 1
Рассмотрим все числа, соответствующие маске 2*1?5?1 и не превышающие $10^8$. Проверяем варианты с пустой, одноразрядной и двухразрядной последовательностью вместо символа «*».
- 2
Для семизначного варианта число имеет вид $210501+1000a+10b$. Перебор цифр $a$ и $b$ с проверкой делимости на 1921 даёт число 213231.
Ещё 2 шага — в полном решении
Пусть $R$ — сумма различных натуральных делителей целого числа, не считая единицы и самого числа. Напишите программу, которая перебирает целые числа, большие $500\,000$, в порядке возрастания и ищет…
- 1
Перебираем числа, начиная с $500001$, и для каждого вычисляем сумму его собственных делителей.
- 2
Для числа $500022 = 2 \cdot 3^2 \cdot 27779$ сумма всех делителей равна $3 \cdot 13 \cdot 27780 = 1083420$, поэтому $R = 1083420 - 1 - 500022 = 583397$.
Ещё 1 шаг — в полном решении
37ФИПИ 967872№ 25Повышенная Напишите программу, которая перебирает целые числа, большие 600000, в порядке возрастания и ищет среди них такие, у которых есть натуральный делитель, оканчивающийся на цифру 8 и не равный ни самому…
- 1
Последовательно проверяем целые числа, большие 600000, и перебираем их делители от наименьшего к наибольшему.
- 2
Для числа 600012 наименьший подходящий делитель — 18.
Ещё 4 шага — в полном решении
38ФИПИ 9C9EF1№ 25Повышенная Напишите программу, которая перебирает целые числа, большие 500000, в порядке возрастания и ищет среди них такие, у которых есть натуральный делитель, оканчивающийся на цифру 8 и не равный ни самому…
- 1
Перебираем целые числа, большие 500000, и для каждого ищем делители, оканчивающиеся на цифру 8. Само число и делитель 8 исключаются.
- 2
Число 500004 делится на 18, поэтому первая найденная пара — 500004 и 18.$$500004 \div 18 = 27778$$
Ещё 2 шага — в полном решении
Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы: символ «?» означает ровно одну произвольную цифру; символ «*» означает любую последовательность…
- 1
Длина числа не превышает 8 цифр. Поэтому вместо символа «*» может находиться от 0 до 3 цифр.
- 2
При отсутствии цифр или при одной-двух цифрах проверка остатков по модулю 133 не даёт допустимого значения вставки.
Ещё 3 шага — в полном решении
Пусть $M$ — сумма минимального и максимального натуральных делителей целого числа, не считая единицы и самого числа. Если таких делителей у числа нет, то считаем значение $M$ равным нулю. Напишите…
- 1
Для каждого составного числа находим минимальный собственный делитель $p$. Максимальный собственный делитель равен $n / p$, поэтому $M = p + n/p$.$$M = p + \dfrac{n}{p}$$
- 2
Проверяем числа по возрастанию, начиная с $452\ 022$, и оставляем те, для которых $M \bmod 7 = 3$.
Ещё 2 шага — в полном решении