3
$\begingroup$

$ ω(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;
        }
    }
}
$\endgroup$
10
  • 3
    $\begingroup$ 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) ? $\endgroup$
    – reuns
    Jun 18, 2020 at 0:32
  • $\begingroup$ 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}) $ $\endgroup$
    – Lakshman
    Jun 18, 2020 at 4:54
  • $\begingroup$ 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. $\endgroup$
    – Peter
    Jun 18, 2020 at 8:14
  • $\begingroup$ @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 $ $\endgroup$
    – Lakshman
    Jun 18, 2020 at 8:18
  • 3
    $\begingroup$ 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)$. $\endgroup$ Jun 23, 2020 at 19:00

0

You must log in to answer this question.