Арифметические алгоритмы (Теория чисел)

На Марсе строится колония! Каждому жилому модулю присваивается номер от 1 до N. По марсианским законам, модули с простыми номерами получают улучшенную систему жизнеобеспечения.

Глава колонии хочет знать:
1. Сколько модулей получат улучшенную систему?
2. Какие именно это модули?

ВХОДНЫЕ ДАННЫЕ:
Одно число N (1 ≤ N ≤ 10^7) - количество модулей.

ВЫХОДНЫЕ ДАННЫЕ:
Первая строка: количество простых чисел от 2 до N.
Вторая строка: все простые числа от 2 до N через пробел (в порядке возрастания).
Если простых чисел нет, во второй строке ничего не выводить.

 

 

Примеры

№	Входные данные	Выходные данные
1	4 23 23456 7 17	22 11712 6 16

Напишите программу, которая в последовательности натуральных чисел подсчитывает количество тех чисел, которые одновременно удовлетворяют двум условиям:

1. Оканчиваются на 0 в системе счисления с основанием 9;
2. Не оканчиваются на 0 в системе счисления с основанием 7.

Формат входных данных

В первой строке задаётся количество элементов \(N\) (\(1 \le N \le 1000\)). В каждой из следующих \(N\) строк — одно натуральное число.

Формат выходных данных

Одно целое число — количество подходящих чисел.

Шарик украшает ёлку гирляндой из N лампочек. Лампочки мигают по очереди: первая загорается в момент времени 0, вторая — в момент 1, третья — в момент 2, и так далее. Когда загорается последняя лампочка, следующей снова загорается первая, потом вторая и т.д.

Шарик хочет узнать, какая по счёту лампочка будет гореть в момент времени T.

Входные данные: Два целых числа N и T (1 ≤ N ≤ 1000, 0 ≤ T ≤ 10⁹) — количество лампочек и момент времени.

Выходные данные: Номер лампочки, которая горит в момент T.

Мама прислала Дяде Фёдору посылку с конфетами. Дядя Фёдор хочет разделить конфеты поровну между собой, Матроскиным и Шариком. Если конфеты не делятся на троих поровну, остаток достанется Галчонку.

Сколько конфет получит каждый из троих друзей, и сколько останется Галчонку?

Входные данные: Одно целое число N (1 ≤ N ≤ 10000) — количество конфет в посылке.

Выходные данные: Два числа через пробел: сколько конфет получит каждый из друзей и сколько достанется Галчонку.

На Discord-сервере игрок получает VIP-статус, если количество его сообщений кратно 25 и при этом не менее 300.​

Напишите программу, которая запрашивает у пользователя количество сообщений и определяет, получит ли игрок VIP-статус.

Входные данные: количество сообщений (целое положительное число)

Выходные данные:

• VIP — если количество сообщений кратно 25 и не менее 300

• NO — в остальных случаях

В магазине Roblox действует специальная скидка: игрок получает её, если сумма его покупки кратна 50 и при этом не менее 200 робуксов.​

Напишите программу, которая запрашивает у пользователя сумму покупки и определяет, получит ли игрок скидку.

Входные данные: сумма покупки в робуксах (целое положительное число)

Выходные данные:

• YES — если сумма кратна 50 и не менее 200

• NO — в остальных случаях

Современные компьютеры состоят из микроскопических транзисторов (электронных переключателей). Каждый из них может быть в двух состояниях:

• 1 (ВКЛ) — есть ток → True

• 0 (ВЫКЛ) — нет тока → False

Какое число соответствует True в двоичном коде?

Словом Чемпернауна называется длинная строка, полученная из натуральных чисел, записанных подряд без пробелов и запятых. Так, для десятичной системы счисления слово Чемпернауна начинается с 123456789101112…, а для семеричной – с 1234561011121314151620…
Найдите, какие цифры стоят на заданных местах (индексах) в слове Чемпернауна, записанном в семеричной системе счисления. Например, под индексом 3 находится цифра «4», а под индексом 1 цифра «2» – нумерация начинается с нуля.

Формат входных данных
На вход программе в первой строке подается натуральное число N (N ≤ 1000) – количество индексов, для которых надо определить цифру в записанном в семеричной системе слове Чемпернауна. Во второй строке даётся последовательность из N неотрицательных чисел, разделённых пробелами, каждое из которых не превосходит 2*10⁹ – индексы, для которых надо найти цифру. Нумерация индексов начинается с 0.

Формат выходных данных
Вывести строку из N цифр – цифр, стоящих на заданных местах в слове Чемпернауна, записанном в семеричной системе счисления.

В мире двоичных чисел произошёл масштабный сбой, теперь двоичные числа разучились складываться друг с другом. Притом спустя часть времени была выявлена закономерность новых правил сложения, она оказалась следующей:

• 1 + 1 = 0
• 1 + 0 = 1
• 0 + 1 = 0
• 0 + 0 = 1

Таким образом было выявлено, что также порядок слагаемых имеет значение (первое слагаемое число верхнее, второе – нижнее). Так как все эти правила теперь запомнить было очень сложно, то попросили разработать алгоритм, который будет принимать два двоичных числа одинаковой длины и возвращать результат суммы этих двух чисел в столбик.

Формат входных данных
На первой строке подаётся первое слагаемое – двоичное число без значащих нулей длины N (1 <= N <= 10⁵).
На второй строке подаётся второе слагаемое – двоичное число без значащих нулей также длины N.

Формат выходных данных
Вывести на первой строке результат суммы двух двоичных чисел. Если в результате есть незначащие нули, то выводить без них. Если получился 0, то вывести просто 0.

На доске были выписаны два квадрата натуральных чисел: \(x^2\) и \(y^2\), где \(l \le y^2 < x^2 \le r\). Числа \(x^2\) и \(y^2\) стерли и выписали на доске их разность \(d\).

По заданным \(l\), \(r\) и \(d\) выясните, сколько различных пар натуральных чисел \(x^2, y^2\) могло быть выписано на доске.

Формат выходных данных
В первой строке даны три числа \(d\), \(l\) и \(r\) (\(1 \le d \le 10^9, 1 \le l \le r \le 10^{18}\)).

Формат входных данных
Выведите количество подходящих пар квадратов.

Примечание
В первом примере подходят числа 100 и 36. Во втором примере также подходят числа 256 и 196.

Дед мороз получил очень странное послание! Помогите ему. Напишите программу, которая выводит это сообщение в понятной форме 

–Т—Л–≤–µ–і–Є—В–µ –і–≤–∞–і—Ж–∞—В—М –њ–µ—А–≤—Л—Е –њ—А–Њ—Б—В—Л—Е —З–Є—Б–µ–ї
 

Муми-Тролли хотят украсить свою ёлку гирляндами, чтобы она светилась во время новогоднего праздника. Известно, что длина всех витков гирлянды, необходимых для полного обвивания ёлки, составляет L метров. Каждая гирлянда имеет длину M метров. Помогите муми-троллям посчитать сколько всего гирлянд необходимо муми-троллям?

Формат входных данных
В первой строке записано натуральное число L (L < 10⁹). Во второй строке - натуральное число M (M < 10⁹).

Формат выходных данных
Выведите одно число - количество необходимых гирлянд

По введенному натуральному числу K, не превосходящему 1 000 000, выдать K-ое по счету простое число.

Входные данные
Во входном файле находится одно натуральное число K.

Выходные данные
В выходной файл выведите K-е простое число.

Вывести представление целого числа N в виде произведения простых чисел.

Входные данные
В первой строке находится единственное число N. 2 <= N <= 2³¹ - 1.

Выходные данные
Выводится список чисел в порядке неубывания, разделённых знаком "*".

Вывести все простые числа от M до N включительно.

Входные данные
В первой строке находятся разделённые пробелом M и N. 2 <= M <= N <= 300 000.

Выходные данные
Вывести числа в порядке возрастания, по одному в строке. Если между M и N включительно нет простых - вывести "Absent".

На странице сайта размещена карусель с фотографиями. Фотографии в каруселе пронумерованы от 1 до n. Карусель содержит кнопки вперед и назад. При нажатии кнопки вперед, в карусель загружается следующая фотография (фотография с номером на 1 больше). Если в каруселе отображается последняя фотография (с номером n), то при нажатии кнопки вперед загружается первая фотография (фотография с номером 1).
Всего карусель содержит n фотографий. Посетитель сайта сейчас просматривает фотографию с номером m. Фотография под каким номером загрузится в карусель, если посетитель нажмет один раз кнопку вперед?

Формат входных данных
Программа получает на вход две строки. В первой строке записано натуральное число n (n < 10⁹). Во второй - натуральное число m (1≤ m ≤ n). 

Формат выходных данных
Выведите одно число - номер следующей фотографии.

От организаторов олимпиады поступил заказ на покупку N пачек бумаги "Снегурочка". Магазин упаковывает бумагу по M пачек бумаги в одну коробку. Последняя коробка может быть неполной. Определите, какое количество пачек бумаги будет в последней коробке. 

Формат входных данных
В первой строке входных данных записано натуральное число N - количество пачек, которые были заказаны. Во второй строке - натуральное число M - максимальное число пачек, которое помещается в одну коробку.

Формат выходных данных
Выведите одно число - ответ на задачу

Переведите натуральное число из двоичной системы в десятичную (в двоичном числе не более 10 цифр).

Входные данные
Вводится натуральное число, записанное в двоичной системе.

Выходные данные
Выведите число, записанное в десятичной системе.

Кате нравятся целые числа, которые делятся без остатка на число K, а Маше — целые числа, которые делятся без остатка на число M. Сегодня подруги решили утроить соревнование и выяснить, чьи любимые числа лучше.

Для начала они выписали на лист бумаги все целые числа от A до B включительно. Затем Катя посчитала, сколько чисел среди выписанных делятся на число K без остатка, а Маша посчитала, сколько чисел делятся на число M без остатка.

В соревновании победит та из них, чьих любимых чисел окажется больше. Если же количества любимых чисел Кати и Маши совпадут, объявляется ничья. Для того, чтобы определить победителя, девочки попросили вас вычислить разность количества любимых чисел Кати и Маши.

Входные данные

Программа получает на вход четыре целых положительных числа, записанных в отдельных строках: K, M, A и B. Числа не превосходят 2×10⁹.

Выходные данные

Программа должна вывести одно целое число — разность количества любимых чисел Кати и количества любимых чисел Маши.
 

Примеры

Ввод	Вывод	Пояснение
2 3 2 9	1	Выписаны числа 2, 3, 4, 5, 6, 7, 8, 9. Среди них есть четыре числа, которые делятся на 2: 2, 4, 6, 8, и три числа, которые делятся на 3: 3, 6, 9. Ответ: 4 - 3 = 1.
3 3 6 6	0	Выписано одно число 6 и оно является любимым числом как Кати, так и Маши.
10 2 1 5	-2	Среди чисел 1, 2, 3, 4, 5 нет ни одного любимого числа Кати, а у Маши любимыми являются 2 и 4.