e-olymp 3843. Простые

Задача

Пусть $m$ и $n$ $\left(2 ≤ m < n ≤ 107\right)$ — целые числа. Рассмотрим следующее множество:

Prime $\left(m, n\right) = \lbrace{ p | p\;простое, m ≤ p ≤ n \rbrace}$.

Вычислить мощность множества Prime$\left(m, n\right)$.

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

Состоит из нескольких тестов. Два последовательных теста разделены пустой строкой. Для каждого теста в отдельной строке заданы числа $m$ и $n$.

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

Для каждого теста вывести результат в отдельной строке. Результаты соседних тестов разделять пустой строкой. Для каждого теста вывести мощность множества Prime$\left(m, n\right)$.

Тесты

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

70    110

5    150

8

10

33

7    2056

14    181

27    367

307

36

64

77    777

55    555

33    333

116

85

56

Код решения

 

Решение

Для решения этой задачи требуется завести большой массив типа bool и присвоить ему значение true. Затем проверяется, простое ли число, если это не так, то присваиваем значение false.
Затем нужно последовательно сосчитать мощность каждого множества простых чисел, то есть количество простых чисел от n до m, с помощью массива-счётчика: записывается в него прошлые и последующие элементы множества простых чисел.
После этого в цикле задаются нужные значения, считается ответ и выводится.

Условие задачи на e-olymp.com
Код решения на ideone.com

e-olymp 388. Превращение

Условие

Возьмем какое-нибудь натуральное число [latex]N[/latex]. Будем изменять его следующим образом: если число четное, то разделим его на [latex]2[/latex], если нечетное, прибавим [latex]1[/latex]. После нескольких таких изменений мы всегда получаем число [latex]1[/latex]. Например, из числа [latex]11[/latex] получается число [latex]12[/latex], затем [latex]6[/latex], [latex]3[/latex], [latex]4[/latex], [latex]2[/latex] и, наконец, [latex]1[/latex]. Таким образом, для получения [latex]1[/latex] из [latex]11[/latex] нужно проделать [latex]6[/latex] изменений.

Напишите программу, которая считывает натуральное число и выводит количество изменений данного числа до получения [latex]1[/latex].

Тестирование

Входные данные Выходные данные
1 1 0
2 11 6
3 65 13
4 1024 10

Код

Решение

Так как в качестве ответа на задачу нам нужно вывести значение переменной-счетчика, которая отвечает за количество проделанных изменений, то объявлять ее нужно будет не в начальных условиях цикла for, а в пределах главной функции:

Теперь опишем, каким образом будет работать цикл:

  • Цикл начинается со значением счетчика 0, так как возможны случаи, когда операций над [latex]n[/latex] вообще не нужно будет производить (конкретно — при [latex]n=1[/latex]).
  • Поскольку нам гарантируют, что входное число [latex]n[/latex] — натуральное, то цикл будет работать до тех пор, пока [latex]n>1[/latex].
  • После каждой итерации значение счетчика будет увеличено на [latex]1[/latex].
  • Тело цикла состоит из единственного оператора присваивания переменной с числом [latex]n[/latex] нового значения. [latex]n[/latex] может быть преобразовано двумя способами, и для определения нужного используется проверка на его четность:
    • если [latex]n[/latex] — нечетное, то значение [latex]n[/latex] увеличивается на [latex]1[/latex];
    • в противном случае [latex]n[/latex] делится на [latex]2[/latex].

Реализуем описанный алгоритм, после которого отправляем на печать значение счетчика i:

Ссылки

Условие задачи на E-Olymp;

Код программы на Ideone.com;

Подтверждение решения на E-Olymp.

e-olymp 63. Анфиса и цветы

Задача. Анфиса и цветы

Условие задачи

 Мурзик одну из цветочных клумб сделал в виде шахматной доски размерами [latex]m[/latex] на [latex]n[/latex], в каждой клеточке которой растет какой-то цветок. Иногда на эту клумбу он выводит на прогулку Анфису (да, не удивляйтесь, они действительно друзья). Анфиса, начиная всегда с верхнего левого угла передвигается по клумбе к правому нижнему и собирает цветы, причем таким образом, чтобы каждый раз проходить новым маршрутом, а Мурзик на выходе вручает ей кусочек сыра.

Посчитать, какое наибольшее количество кусочков сыра получит Анфиса, если она все время старается сохранить как можно больше цветов. При каждом очередном своем проходе Анфиса обязательно должна собрать как минимум один цветок.

<

h4″>Входные данные

В одной строке заданы два числа m и n [latex]\left( n, 0 < m, n ≤ 2\cdot 10^9 \right)[/latex].

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

Вывести наибольшее количество кусочков сыра, которые может получить Анфиса.

Также условие задачи можно посмотреть здесь.

Реализация

Тестирование

Входные данные (m, n) Выходные данные
1 2, 3 3
2 3, 3 5
3 3, 4 7
4 4, 3 7
6 5, 7 25

Алгоритм решения

Задана цветочная клумба в виде шахматной доски размерами [latex]m[/latex] на [latex]n[/latex]. Очевидно, что количество цветов на данной клумбе равно [latex]m\cdot n[/latex]. Пусть Анфиса, совершая свое очередное передвижение, начиная с левого верхнего угла клумбы и направляясь к правому нижнему,  съедает latex\cdot(n-1)[/latex]  цветов, так как, согласно условию задачи, Анфиса обязательно должна собрать как минимум один цветок при каждом проходе. После каждого такого прохода на выходе она получает один кусочек сыра.

Следовательно, имеет место следующая формула: [latex]p=(m-1)\cdot(n-1)+1[/latex], где p — наибольшее количество кусочков сыра, которое может получить Анфиса. Действительно, если [latex]m=2[/latex], [latex]n=3[/latex], то получаем [latex]p=3[/latex].

Ссылка на засчитанное решение.

Для запроса на выполнение нажать здесь.