Problem:
Given natural number N, count $\sum_{k\le N} [{\omega(k)=4}]$
This is the sequence of $\omega(k)=4$, we don't need to generate the sequence. Given a $N$, we need to know number of numbers in the sequence that are less than or equal to $N$.
You can assume $O(n^{2/3})$ memory is available.
Clarification:
primeomega(n) or $\omega(n)$ denotes count of number of distinct prime factors of a natural number $n$. For example $\omega(12)=2$ as its factors are {2,2,3} since we consider only distinct prime factors; whereas $\omega(6)=2$ as well as $\omega(36)=2$ . I am interested in counting $\sum \omega(i)= SomeValue$, to be particular $SomeValue \ge 4$ since smaller $SomeValue$ seems trivial.
My Thoughts:
The most brute force approach is to visit each number and factorise spending time complexity of $O(N.N^{1/4})=O(N^{5/4})$. Obviously that won't cut it. I need a sublinear algo.
I am thinking on lines of expressing one omega's recurrence in terms of another, something like: $f(N=100,w=4) = K*f(N=100/prime_{i},w=3)$ in a way it can be expressed in something similar to Legendre's prime counting function . For that sieving primes till $N^{1/2}$ might be necessary. My ideas are far from concrete, needs lot of refinement.
To summarise:
- Expected Time Complexity: $O(n^{3/4})$ or better
- Expected Space Complexity: $O(n^{2/3})$ or better