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

06/06/2018 by Илья Черноморец

Задача

Пусть $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

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

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

2 20

70 110

5 150

7 2056

14 181

27 367

307

77 777

55 555

33 333

116

Код решения

#include <iostream>
#include <cmath>
using namespace std;


int main()
{
     int n, m;  
     const int MAXN = 10000001;
     bool simple[MAXN];
     for(int i = 2; i <= MAXN; i++){
         simple[i] = true;
     }
     for(int i = 2; i <= sqrt(MAXN); i++){
         if(simple[i]){
             for(int j = i * i; j <= MAXN; j += i){
                 simple[j] = false;
             }
         }
     }

     int count[MAXN];
     int lastSum = 0;
     for(int i = 1; i < MAXN; i++){
         count[i] = lastSum + simple[i];
         lastSum = count[i];
     }
     while(cin >> m >> n){
         int answer = count[n] - count[m] + simple[m];
         cout << answer << endl << endl;
     }
}

#include <iostream>

#include <cmath>

using namespace std;

int main()

{

int n, m;

const int MAXN = 10000001;

bool simple[MAXN];

for(int i = 2; i <= MAXN; i++){

simple[i] = true;

}

for(int i = 2; i <= sqrt(MAXN); i++){

if(simple[i]){

for(int j = i * i; j <= MAXN; j += i){

simple[j] = false;

}

int count[MAXN];

int lastSum = 0;

for(int i = 1; i < MAXN; i++){

count[i] = lastSum + simple[i];

lastSum = count[i];

}

while(cin >> m >> n){

int answer = count[n] - count[m] + simple[m];

cout << answer << endl << endl;

}

Решение

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

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

Related Images:

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

30/09/2015 by Молоканов Юрий

Условие

Возьмем какое-нибудь натуральное число [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

Код

#include <iostream>
using namespace std;

int main() {
	int n, i;	// n для числа, i для счета преобразований
	cin >> n;
	for (i = 0; n > 1; i++) n = (n%2>0?n+1:n/2);	// Преобразовываем n, пока не получим 1
	cout << i;	// Выводим значение счетчика
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, i; // n для числа, i для счета преобразований

cin >> n;

for (i = 0; n > 1; i++) n = (n%2>0?n+1:n/2); // Преобразовываем n, пока не получим 1

cout << i; // Выводим значение счетчика

return 0;

}

Решение

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

#include <iostream>
using namespace std;

int main() {
	int n, i;	// n для числа, i для счета преобразований

#include <iostream>

using namespace std;

int main() {

int n, i; // n для числа, i для счета преобразований

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

Цикл начинается со значением счетчика 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:

for (i = 0; n > 1; i++) n = (n%2>0?n+1:n/2);
cout << i;

1 2	for (i = 0; n > 1; i++) n = (n%2>0?n+1:n/2); cout << i;

Ссылки

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

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

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

Related Images:

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

14/09/2015 by Кудымовская Вика

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

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

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

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

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

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

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

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

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

Реализация

#include <iostream>     
using namespace std;
int main () {
    long m, n, p;
    cin >> m >> n;
    p = (m * n - (m + n - 1)) + 1;
    cout << p << endl;
    return 0;
}

#include <iostream>

using namespace std;

int main () {

long m, n, p;

cin >> m >> n;

p = (m * n - (m + n - 1)) + 1;

cout << p << endl;

return 0;

}

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

№	Входные данные (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].

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

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

C++ для приматов

Начальный курс программирования для студентов направления "Прикладная математика" Одесского национального университета имени И.И.Мечникова

Tag Archives: множество натуральных чисел

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

Задача

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

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

Тесты

Код решения

Решение

Related Images:

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

Условие

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

Код

Решение

Ссылки

Related Images:

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

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

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

Related Images: