From 96254947699986c59f0dc63d69fd4b76bd3ed43e Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Mon, 6 Jul 2026 19:08:08 +0200 Subject: Initial commit --- 07_mathematics/counting_divisors_1713.cpp | 34 +++++++++++++++++++++++++++++++ 1 file changed, 34 insertions(+) create mode 100644 07_mathematics/counting_divisors_1713.cpp (limited to '07_mathematics/counting_divisors_1713.cpp') diff --git a/07_mathematics/counting_divisors_1713.cpp b/07_mathematics/counting_divisors_1713.cpp new file mode 100644 index 0000000..fe30ab4 --- /dev/null +++ b/07_mathematics/counting_divisors_1713.cpp @@ -0,0 +1,34 @@ +#include +#include + +constexpr size_t max = 1000001; +std::array spf; // Smallest prime factor of i + +size_t ndiv(size_t x) { + size_t n{1}, d{0}, e{0}; + for (size_t i = x; i > 1; i /= spf[i]) { + if (spf[i] != d) { + n *= e+1; + d = spf[i]; + e = 1; + } else e++; + } + return n * (e+1); +} + +int main() { + for (size_t i = 2; i < max; i++) { + if (spf[i] != 0) continue; + spf[i] = i; + for (size_t j = 2; i*j < max; j++) + if (spf[i*j] == 0) + spf[i*j] = i; + } + + size_t n, x; + std::cin >> n; + for (size_t i = 0; i < n; i++) { + std::cin >> x; + std::cout << ndiv(x) << "\n"; + } +} -- cgit v1.3