Count number of prime factor p of $a!$
(Mylib/Number/Prime/factorial_prime_factorization.cpp)

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00

Operations

Requirements

Notes

Problems

• Codeforces Round #589 (Div. 2) C. Primes and Multiplication

References

Code

#pragma once
#include <cstdint>

namespace haar_lib {
  int64_t factorial_prime_factorization(int64_t a, int64_t p) {
    int64_t ret = 0, q = p;

    while (q <= a) {
      int64_t t = a / q;

      ret += t;

      int64_t k;
      if (__builtin_smulll_overflow(q, p, (long long int*) &k)) break;

      q = k;
    }
    return ret;
  }
}  // namespace haar_lib

#line 2 "Mylib/Number/Prime/factorial_prime_factorization.cpp"
#include <cstdint>

namespace haar_lib {
  int64_t factorial_prime_factorization(int64_t a, int64_t p) {
    int64_t ret = 0, q = p;

    while (q <= a) {
      int64_t t = a / q;

      ret += t;

      int64_t k;
      if (__builtin_smulll_overflow(q, p, (long long int*) &k)) break;

      q = k;
    }
    return ret;
  }
}  // namespace haar_lib

Back to top page