Тренировка #2 [Меньшиков]

[Условия задач]                   [Список тренировок]

2A. Простые числа
[primes2] Идентично [primes]
Первая задача [primes] проходит даже если перебирать в качестве делителей все числа в интервале [2,sqrt(n)]. Вторая же задача [primes2] проходит только, если перебирать нечетные делители.
[primes2] Precalc всех простых чисел
Предыдущую реализацию можно ускорить если в качестве делителей использовать не просто нечетные числа, а простые. Ускорение ~ в 2 раза.
[primes2] Решето Эратосфена
Решето Эратосфена упоминается в учебниках по математики за 6 класс. Сам подход несложен и вполне понятен. Реализация лаконична и не представляет сложности. Ко всему прочему это наиболее эффективный подход к нахождению простых чисел в заданном интервале. 
2B. Перестановки
[permut] Рекурсивная реализация
Одна из классических реализаций. На i-ое место текущей перестановки ставим одно из неиспользованных значений первоначальной комбинации. Таким подходом достигается генерация всех перестановок в лексикографическом порядке.
[permut] next_permutation
Бывают случаи, когда нужно сгенерировать перестановку следующую за данной в лексикографическом порядке. Такая функция определена в STL и называется next_permutation(). Здесь представлена самописная реализация этой функции. Поподробнее об ее реализации можно почитать в книге Окулова "Программирование в алгоритмах"
2C. Маршрут
[route] Вариант 1
Задача представляет собой модификацию классической задачи на динамику “Черепашка”. В данной реализации для восстановления пути каждый элемент хранил направление движения ‘i’(начальная точка) ‘l’(слева) ‘u’(сверху), которое характеризовало откуда мы пришли в данную ячейку, двигаясь оптимальным образом. 
[route] Вариант 2
В данной реализации для восстановления пути мы изначально присвоили нулевой строке и нулевому столбцу граничные значения, чтобы не выйти за пределы матрицы. В текущей задаче мне кажется этот подход более предпочтителен.
2D. Пересечение отрезков
[segments]
Идею решения позаимствовал у команды HardFire, за что им выражаю благодарность.
2E. Длинная сумма
[longsum]
Наверное самая распространенная задача на длинную арифметику. Часто ее можно встретить в задачах на динамику, где нужно найти количество способов сделать определенное действие.
2F. Спираль
[spiral]
Хорошая задача для начинающих. В реализации думаю очень уместно использовать массив движений.

[Все решения]