Помогите в решении задачи

[Virel7779]

Дано целое число N (N<=10^9) и выражение -- n!/n^k=целое число;
Нужно найти найбольшее вероятно число k. Очень прошу помочь, уже 4 дня ломаю голову без остановки(



(Не могу написать саму программу на Паскале)

[type_Oleg]

Не можете математически найти решение, или программу на Паскаль не можете составить ( например, тупо перебором ) ?

PS Хотя факториал 10^9 - это конечно круто.. Даже трудно представить сколькизначное число .

[Virel7779]

Не могу написать саму программу
Уже было множество идей но 10^9 слишком огромно для них

Лично у меня перебор после 10^6 занимает огромное время

[type_Oleg]

Ну, ясно что для любого n число k >= 1, ибо:
n!/n^k = (n-1)!/n^(k-1)
т.е. одно n всегда сокращается

[Virel7779]

Я это понимаю, но мне это не помогает)

[Virel7779]

Я пробывал разбивать n на простые множители через решето Эратосфена, и потом сравнивать количество простых множителей числа с количеством этих простых множителей факториала.
Увы не работает.(Надеюсь я нормально объясняю)

[Serge_Bliznykov]

Нужно найти найбольшее вероятно число k.

простите за тормознутость, а что именно нужно найти?

[Virel7779]

Найбольшую степень числа n(k и есть степень), что-бы n!/n^k=цельному числу
Например для числа 12 k=5, для 13 k=1.

12^5 = 248832 делит 12! = 479001600 (479001600/248832 = 1925), а 12^6 = 2985984 (479001600/2985984=160,416(6) ) нет.

[Аватар]

  j:=Trunc(Sqrt(n));
  if j*j=n then Dec(j);
  k:=1;
  for i:=2 to j do if n mod i = 0 then Inc(k);

Ответ в k

УПС, ответ неверен, упустил, что еще может сокращаться

[Virel7779]

Не находит максимальный k для некоторых чисел.
На 12 выводит k=3;
12^5 = 248832 делит 12! = 479001600 (479001600/248832 = 1925).