Untitled

mail@pastecode.io avatar
unknown
plain_text
2 months ago
808 B
3
Indexable
Never
#include <iostream>

const int N = 2000001;

using namespace std;

int f[N], d[N];

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) f[i] = 0;
    for (int i = 2; i <= n; i++) {
        if (f[i] == 0) {//i -- простое
            for (int j = 1; i * j <= n; j++) { //i, 2i, 3i, 4i, 5i, 6i...
                int k = i * j;
                if (f[k] == 0) f[k] = i;
            }
        }
    }
    int ans = 1;
    d[1] = 1;
    for (int i = 2; i <= n; i++) {
        int x = i;
        int alpha = 0;
        //alpha -- степень простого f[i]
        //cout << f[i] << endl;
        while (x % f[i] == 0) {
            x /= f[i];
            alpha++;
        }
        d[i] = d[x] * (alpha + 1);
        ans = max(ans, d[i]);
    }
    cout << ans;
    return 0;
}
Leave a Comment