Первичная факторизация n факториала

Question

Как найти простую факторизацию n! когда n большое число (10^8)? Какой самый эффективный способ сделать это?

Answer 1

Начните с поиска простых чисел до $n$, возможно, с помощью сита Эратосфена. Затем пометьте самые большие простые числа как имеющие показатель 1, вплоть до (но не включая) n/2. Затем отметьте те из n / 2 до n/3 как имеющие показатель степени 2 и т. Д.; продолжайте до тех пор, пока не доберетесь до sqrt(n). В этот момент вы можете также рассчитать каждый показатель в отдельности с помощью этой функции (псевдокод):

factorial_exponent(n, p):
  n <- floor(n/p)
  let t = n
  while n >= p:
    n <- floor(n/p)
    t <- t + n
  return t

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