Đếm ước của một số $O(sqrt(n))$

long long countDiv(long long n)
{
	long long cnt = 0;
	for(int i=1; 1ll*i*i <= n; i++)
	{
		if(n % i == 0)
		{
			if(n / i == i) cnt++;
			else cnt += 2;
		}
	}
	return cnt;
}

Lấy các ước của một số $O(sqrt(n))$

vector<int> Div;
void countDiv(long long n)
{
	for(int i=1; 1ll*i*i <= n; i++)
	{
		if(n % i == 0)
		{
			if(n / i == i) Div.pb(i);
			else
			{
				Div.pb(i);
				Div.pb(n/i);
			} 
		}
	}
}

Đếm ước nâng cao cho nhiều số và mỗi lần truy vấn $O(1)$:

long long cntDiv[N+5];
for(int i = 1; i*i <= N; i++) 
        for(int j = i*i; j <= N; j+=i) 
            cntDiv[j]++; 
for(int i = 1; i <= N; i++) cntDiv[i]*=2; 
for(int i = 1; i*i <= N; i++) cntDiv[i*i]--;