# Computing $w(n)$ : How many integer in range$1..n$ have distinct prime divisor equals to k.

$$ω(n)$$ is the number of distinct prime divisor of $$n$$. Here I am trying to find how many integer in given range $$1, \ldots, n$$ have $$ω(n) = K$$. Constraints given on $$n$$ is $$n \le 10^{12}$$.

I can easily compute $$ω(n)$$ for $$n \le 10^{8}$$ in $$O (n \log \ n)$$ .

Below code can compute distinct prime divisors in $$O(n \log \ n)$$.

How to compute when $$n \le 10^{12}$$

void genPrimes(){
vector<bool>isPrimes(MAX,1);
for(int i=2;i*i<MAX;i++){
if(isPrimes[i]){
for(int j=i;i*j<MAX;j++) isPrimes[i*j]=0;
}
}

primes.push_back(2);
for(int i=3;i<MAX;i+=2){
if(isPrimes[i])primes.push_back(i);
}
}

void genDistPrimeFactors(){
for(int i=0;primes[i]<1000001;i++){
for(int j=2*primes[i];j<1000001;j+=primes[i]){
divs[j]+=1;
}
}
}

• With Erathosthenes sieve it becomes $O(n\log \log n)$ and since $O(n)$ is a lower bound you can't expect much better. $O(n \log n)$ is already not bad. What is your problem, the huge amount of needed memory (making the program much slower) ? Jun 18, 2020 at 0:32
• With above approach is not feasible to compute $w(n) \ for \ n <= 10^{12}$. I think There must be an algorithm which can compute it in $O(sqrt(n))$ memory and $w(n)$ in somewhat $O(n^{2/3})$ Jun 18, 2020 at 4:54
• Do you need the exact number for every $k$ ? In this case, I do not think that there is a significant better way. In your case, we have $\omega(n)\le 11$. The larger $k$, the more efficient the number can de determined. Jun 18, 2020 at 8:14
• @Peter "Do you need the exact number for every k ? " Yes, and here $K < 11$. For example $N = 10^8$ then for \ all $k<=8$ $2 = 22724609 3 = 34800362 4 = 25789580 5 = 9351293 6 = 1490458 7 = 80119 8 = 719$ Jun 18, 2020 at 8:18
• The problem becomes a little more tractable when counting the number of integers $x$ in the range $1..n$ for which $\omega(x)=\Omega(x)=k$. For example for $n=10^{12}$ and $k=2$ I get $131125938680$. Also see arxiv.org/pdf/1906.02847.pdf for more information on $\omega(x)$ and $\Omega(x)$. Jun 23, 2020 at 19:00