counting_divisors_1713.cpp (611B)
1 #include <array> 2 #include <iostream> 3 4 constexpr size_t max = 1000001; 5 std::array<size_t, max> spf; // Smallest prime factor of i 6 7 size_t ndiv(size_t x) { 8 size_t n{1}, d{0}, e{0}; 9 for (size_t i = x; i > 1; i /= spf[i]) { 10 if (spf[i] != d) { 11 n *= e+1; 12 d = spf[i]; 13 e = 1; 14 } else e++; 15 } 16 return n * (e+1); 17 } 18 19 int main() { 20 for (size_t i = 2; i < max; i++) { 21 if (spf[i] != 0) continue; 22 spf[i] = i; 23 for (size_t j = 2; i*j < max; j++) 24 if (spf[i*j] == 0) 25 spf[i*j] = i; 26 } 27 28 size_t n, x; 29 std::cin >> n; 30 for (size_t i = 0; i < n; i++) { 31 std::cin >> x; 32 std::cout << ndiv(x) << "\n"; 33 } 34 }