По второй задаче (обратите внимание что первое число в цепочке 1 - кого навело на размышление о простых числах?), алгоритм для решения задачи 2 (правда его характеристики значений по памяти и сложности можно уточнить дополнительно):
P = 1 (будем умножаться)
i = 1
N > 1 (если N = 1 - то цикл есть)
a0: Для каждого N_{i+1}
a1: Если N_{i+1} = 1 то цикл есть
a2: Иначе Если N_{i+1} = простое то
a3: Если P/ делится без остатка - то цикл есть
a4: Иначе - цикла нет
a5: Конец если
a6: Конец если (a2)
a6: Если N_{i+1} = не простое то
a7: раскалдываем на простые N_{i+1} = K_{1}*K_{2}*..K_{M}
и проверяемся на "вхождение" в P
a8: Для каждого простого вхождения K_{j}
a9: Если P/ K_{j} без остатка для всех j - то цикл есть
a10: Иначе цикла нет
a11: Конец для (a8)
a11: Конец если (a6)
a12: P = P*N_{i+1}; умножаемся
a13: Конец для каждого (a0)
Насчет памяти проблем здесь быть недолжно - храним произведение (только влезть бы в разрядность представления чисел), сложность алгоритма определяется сложностью операции разложения на простые и опеределения простоты числа ? O(sqrt(M)*sqrt(N)) - тут надо прикинуть...
P = 1 (будем умножаться)
i = 1
N > 1 (если N = 1 - то цикл есть)
a0: Для каждого N_{i+1}
a1: Если N_{i+1} = 1 то цикл есть
a2: Иначе Если N_{i+1} = простое то
a3: Если P/ делится без остатка - то цикл есть
a4: Иначе - цикла нет
a5: Конец если
a6: Конец если (a2)
a6: Если N_{i+1} = не простое то
a7: раскалдываем на простые N_{i+1} = K_{1}*K_{2}*..K_{M}
и проверяемся на "вхождение" в P
a8: Для каждого простого вхождения K_{j}
a9: Если P/ K_{j} без остатка для всех j - то цикл есть
a10: Иначе цикла нет
a11: Конец для (a8)
a11: Конец если (a6)
a12: P = P*N_{i+1}; умножаемся
a13: Конец для каждого (a0)
Насчет памяти проблем здесь быть недолжно - храним произведение (только влезть бы в разрядность представления чисел), сложность алгоритма определяется сложностью операции разложения на простые и опеределения простоты числа ? O(sqrt(M)*sqrt(N)) - тут надо прикинуть...