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 520. Сумма всех

Сумма всех

Вычислите сумму всех заданных чисел.

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

Содержит [latex]n[/latex] [latex] (1 ≤ n ≤ 10^5) [/latex] целых чисел. Все числа не превосходят [latex]10^9[/latex] по абсолютной величине.

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

Выведите сумму всех заданных чисел.

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 [latex]2[/latex] [latex]4[/latex] [latex]6[/latex]
2 [latex]3[/latex] [latex]3[/latex]
3 [latex]1[/latex] [latex]2[/latex] [latex]3[/latex] [latex]2[/latex] [latex]1[/latex] [latex]9[/latex]
4 [latex]1[/latex] [latex]2[/latex] [latex]3[/latex] [latex]4[/latex] [latex]10[/latex]
5 [latex]0[/latex] [latex]0[/latex] [latex]0[/latex] [latex]0[/latex] [latex]0[/latex]

 

Код программы

Решение задачи

Пользователь вводит числа до тех пор, пока программа не завершит работу. Как только это случается, программа выдаёт ответ в виде суммы всех ранее введённых чисел. Также, стоит использовать переменную типа long из-за того, что сумма чисел может быть довольно большой и явно превышать максимальное допустимое значение для переменной типа int.

Ссылки

• Задача на e-olymp.

• Решение на сайте ideone.

A 325. Простые делители числа

Задача
Дано натуральное число [latex]n[/latex]. Получить все простые делители этого числа.

Входные данные
Натуральное число [latex]n[/latex]

Выходные данные
Все его простые делители напечатанные через пробел

Тесты

входные данные выходные данные
2 2
7 7
50 2 5 5
169 13 13
583 11 53
2368 2 2 2 2 2 2 37
73890 2 3 3 5 821
885066 2 3 7 13 1621
6943960340 2 2 5 97 1787 2003

Код программы

Решение задачи
Для решения задачи мы проверяем все числа от 2 до [latex]\sqrt{n}[/latex]. Если число является делителем [latex]n[/latex], то мы его выводим и делим [latex]n[/latex] на это число. Повторная проверка на простоту не требуется так как мы ведем поиск снизу, а значит число полученное после проверки уже не может делиться на составное. В конце, если остается простой делитель больше, то он выводиться так же.

Ссылки

A328

Задача:
Найти [latex]100[/latex] первых простых чисел.
Тесты:
Обобщим задачу и для тестов используем разное количество первых простых чисел.

Вход Выход
1 25 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97
2 50 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229
3 100 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541

Код:

Решение:
Первое простое число печатаем сразу, остальные [latex]n-1[/latex] будем проверять циклами: проверим нечетные числа на нечетные делители(пройдём цикл по делителям). Число простое, если нет делителей. Если не простое, то переходим к следующему. Каждое простое число печатаем до [latex]n[/latex] включительно.
Ссылки:

  1.  Условие задачи.
  2.  Онлайн компилятор ideone.

e-olymp 1285. Деление Гольдбаха

Задача

Широко известна проблема Гольдбаха! Вот одна из её версий:

  • Любое нечетное число больше [latex]17[/latex] можно записать в виде суммы трёх нечётных простых чисел;
  • Любое чётное число больше [latex]6[/latex] можно записать в виде суммы двух нечётных простых чисел.

Если число чётное, то мы раскладываем его на суммы двух простых разных нечётных, а если нечётное — то на суммы трёх простых разных нечётных. Такой способ разложения для заданного [latex]N[/latex] назовём делением Гольдбаха и обозначим как [latex]G\left( N \right)[/latex].
Зная заданное число [latex]N[/latex], найти [latex]\left| G\left( N \right) \right| [/latex], т.е. количество различных [latex]G(N)[/latex].

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

Входные данные содержат несколько тестовых случаев.
Каждый тест в отдельной строке содержит одно единственное число [latex]N \left( 1\le N\le 20000 \right) [/latex].
Ввод продолжается до конца входного файла.

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

Для каждого тестового случая вывести в отдельной строке одно число — найденное значение [latex]\left| G\left( N \right) \right| [/latex].

Тесты

 №  Входные данные  Выходные данные
 1 5
8
18
19
20
0
1
2
1
2
 2 13
22
78
4
150
0
2
7
0
12
 3 2000 37
 4 6
8
17
19
337
0
1
0
1
195

Код программы

Засчитанное решение на e-olymp.com

Решение

Поместим все тестовые случаи в вектор и найдём максимальное из данных чисел — [latex]max[/latex]. Затем найдём все нечётные простые числа меньшие [latex]max[/latex] (единственное чётное простое число — [latex]2[/latex]). Заведём массив размером [latex]max+1[/latex], [latex]i[/latex]-м элементом которого будет [latex]\left| G\left( i \right) \right| [/latex]. Тогда, если [latex]i[/latex]- чётное, то одно из слагаемых суммы [latex]a_{i}+b_{i}[/latex] двух простых разных нечётных чисел будем подбирать из найденных ранее простых нечётных чисел, но строго меньших [latex]\frac { i }{ 2 } [/latex], чтобы разбиения, отличающиеся только порядком следования частей считать равными, и выполнялось неравенство [latex]a_{i}\neq b_{i}[/latex]. Если разность [latex]i[/latex] и подобранного таким образом числа — нечётное простое число, то это деление Гольдбаха, тогда увеличиваем на единицу [latex]\left| G\left( i \right) \right| [/latex]. Если [latex]i[/latex] — нечётное, то [latex]a_{i}[/latex]из суммы [latex]a_{i}+b_{i}+c_{i}[/latex] трёх простых разных нечётных чисел будем подбирать из всех простых нечётных чисел строго меньших [latex]i[/latex]. Разностью [latex]i[/latex] и подобранного числа [latex]a_{i}[/latex] (разность двух нечётных) будет чётное число [latex]j[/latex], [latex]\left| G\left( j \right) \right| [/latex] мы уже нашли ранее. Тогда можем представить [latex]\left| G\left( j \right) \right| [/latex] различных разложений [latex]G\left( i \right)[/latex] в виде [latex]a_{i}+G\left( j \right)_{k}[/latex] или [latex]a_{i}+{a_j}_{k}+{b_j}_{k}[/latex], где [latex]k=\overline { 1,\left| G\left( j \right)  \right|  }  [/latex], a [latex]G\left( j \right)_{k}[/latex] — [latex]k[/latex]-е разбиение числа [latex]j[/latex]. Значит все полученные [latex]\left| G\left( j \right) \right| [/latex] будем прибавлять к [latex]\left| G\left( i \right) \right| [/latex], а чтоб избежать ситуаций [latex]a_i={a_j}_k[/latex] и [latex]a_i={b_j}_k[/latex], если [latex]i-2a_{i}[/latex] — простое число не равное [latex]a_{i}[/latex] (то есть при некотором значении [latex]k[/latex] одно из чисел [latex] G\left( j \right)_{k} [/latex] равно [latex]a_{i}[/latex] и не равно второму числу, так как [latex]{a_{j}}_k\neq {b_{j}}_k[/latex] мы учли ранее), то будем отнимать единицу от [latex]\left| G\left( i \right) \right| [/latex]. В разбиениях [latex]j[/latex] мы не учитываем порядок следования частей. Чтобы не учитывать его в и разбиениях числа [latex]i[/latex], разделим полученный результат [latex]\left| G\left( i \right) \right| [/latex] на [latex]3[/latex].

Ссылки

A327. Простые числа

Задача из сборника задач по программированию Абрамова С.А. 2000г.
Даны натуральные числа [latex]a, b (a\le b)[/latex]. Получить все простые числа [latex]p[/latex], удовлетворяющие неравенствам [latex]a\le p\le b[/latex].

Входные данные:
Два натуральных числа [latex]a[/latex] и [latex]b[/latex].

Выходные данные:
Некоторое количество натуральных чисел.

Тесты.

Входные данные Выходные данные
[latex]a[/latex] [latex]b[/latex] [latex]p[/latex]
1 1 4 2, 3
2 0 1 Not found
3 5 5 5
4 6 20 7, 11, 13, 17, 19

Код программы (C++).

Код программы (Java).

Решение.
C++:
Для начала, вводятся два целых числа. Очевидно, что придётся проверять, являются ли простыми числа, большие чем [latex]a[/latex] и меньшие чем [latex]b[/latex]. Не представляется возможным заранее узнать, насколько большими будут эти числа, потому, на мой взгляд, наиболее подходящим решением будет каждый запуск программы заново находить все простые числа до [latex]b[/latex]. Создаётся вектор, в котором они будут храниться (целесообразно использовать именно вектор, поскольку неизвестно точно, сколько чисел придётся хранить). Далее идёт цикл, в котором каждое число от двух до [latex]b[/latex], если оно не делится нацело ни на один из элементов вектора (это проверяется при по мощи вложенного цикла), добавляется в этот вектор и, если оно больше чем [latex]a[/latex], выводится. В случае, если [latex]b<2[/latex], очевидно, простые числа найдены не будут, потому выводится "Not found."
Java:
Решение на Java представляет собой реализацию Решета Эратосфена.
Код на ideone.com: C++, Java.
Условие задачи (с.135)