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

Алла Марокко
Алла Марокко

Latest posts by Алла Марокко (see all)

Задача:
Найти [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

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

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

Код на ideone.com
Условие задачи (с.135)

Совершенные числа

Макогон Владимир Сакович
Макогон Владимир Сакович

Latest posts by Макогон Владимир Сакович (see all)

Задача. Найдите все чётные совершенные числа не превышающие заданного числа[latex]M[/latex].

Напомним, что натуральное число [latex]n[/latex] называют совершенным, если оно равно сумме всех своих делителей, не считая его самого. Известно, что все совершенные числа — четные и что первое совершенное число из натурального ряда равно 6. Этим объясняется правило изменения параметра внешнего цикла. Так как все натуральные числа имеют своим делителем единицу, полагаем начальное значение суммы делителей числа S = 1. Во внутреннем цикле организуется перебор всех делителей текущего значения N. Из теории чисел известно, что такому испытанию имеет смысл подвергать числа от 2 до [latex]\frac{n}{2}[/latex], либо даже до [latex]\sqrt{n}[/latex]. Этот не очень совершенный алгоритм реализован в следующем коде:

Обратите внимание, что во внутреннем цикле мы прекращаем искать делители, если их сумма уже превышает исходное число.

Теперь рассмотрим другой подход, позволяющий ускорить вычисления. Используем алгоритм нахождения совершенных чисел, более эффективный по сравнению с приведенным ранее. Этот алгоритм основан на известном из теории чисел утверждении Ферма о том, что если натуральное число [latex]p = 2^{k+1}-1[/latex] простое, то число [latex]n = 2^k \cdot (2^{k+1}-1)=p \cdot 2^k[/latex] — совершенное ([latex]k = 1,2,\ldots[/latex]).
Функция prime() определяет, является ли число [latex]p[/latex] простым. Обратите внимание, что функция проверяет в качестве возможных делителей исходного числа только нечетные числа, так как само испытуемое число — нечетное.

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