Всем привет !Есть интересная задача ,она проходит у меня 30% ,пожалуйста помогите довести до 100% . Моё решение : https://ideone.com/kFiQNK .
Буду рад если вы скажите каким алгоритмом решать эту задачу ! Сама задача :
Найдите число от 1 до N включительно такое, что в разложении его на простые множители количество множителей максимально. Если таких чисел несколько, выберите максимальное из них.
Например, найдем розложение на простые множнители чисел от 1 до 7. Числа 2, 3, 5 и 7 простые, в их разложении по одному множителю. В разложении числа 1 ноль простых множиителей. В разложении чисел 4 = 2·2 и 6 = 2·З по два простых множителя. Значит, ответом к задаче для N = 7 есть число 6.
Входные данные
В первой строке входного файла находится целое число — количество наборов входных данных. Каждый набор состоит из одного целого числа N (1 ≤N < 231 -1).
Выходные данные
Для каждого отдельного тестового примера выведите одну строку, которая будет содержать одно целое число — наибольшее число от 1 до N, количество простых множителей которого максимально, среди всех чисел от 1 до N.
Лимит времени 1 секунда Лимит использования памяти 64 MiB
Входные данные
1 7
Выходные данные
6
Очевидно, что ответом всегда будет число вида 2x или 3 * 2x, перебираешь все такие числа и выбираешь максимальное из них, не превышающее N.
Может для данных ограничений это работает, но для общего случая это не верно.
Что неверно?
Не всегда будут эти числа.
Можете привести контрпример?
144 2 5 3 2 5 1 7 1 13 1
Вот некоторые примеры. Сначала идет количество делителей потом разложение на простые делители в виде простое число и сколько раз оно встречается
Ты задачу неправильно прочитал
Вы, наверное, неправильно поняли суть задания, надо найти число с максимальным количеством множителей в разложении числа на простые делители, а не с максимальным числом делителей
я написал перебором 35% проходит
pow(2,i)лучше заменить на(1<<i), а перебор переменнойiнадо начинать с нуляrotavirus уже проходит %45.Может где-то надо с оптимизировать или другим алгоритмом ?
В заголовке цикла надо не до n идти, а до 30
Спасибо большое , не заметил .