algorithm/divisor range.cpp at main · ihbadhon/algorithm · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

vector<bool> isPrime(mx + 1, true);
vector<int> prime;

void sieve(int mx)
{
    isPrime[0] = false;
    isPrime[1] = false;
    for (ll i = 2; i <= mx; i++)
    {
        if (isPrime[i])
        {
            prime.push_back(i);
            for (ll j = i * i; j <= mx; j += i)
                isPrime[j] = false;
        }
    }
}

vector<int> countDivisorsInRange(int range)
{
    vector<int> divisors(range + 1, 0);
    for (int i = 0; i < prime.size(); i++)
    {
        for (int j = prime[i]; j <= range; j += prime[i])
        {
            int temp = j;
            int cnt = 0;
            while (temp % prime[i] == 0)
            {
                cnt++;
                temp /= prime[i];
            }
            divisors[j] += (cnt + 1);
        }
    }
    return divisors;
}