Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Building on this question, what is the most efficient counting function for distinct prime factors? It would obviously be more efficient if Prime and PrimePi were used instead of PrimeNu, as ybeltukov and Coolwater used in their brilliant solutions to the PrimeOmega counting function question. I was wondering whether there was any way to do something similar in this instance?

The best I have so far is a (very) minor modification of ubpdqn's reply to my previous question:

cnt[k_, n_] := Last@Reap[Sow[1, PrimeNu@#] & /@ Range[n], k, Total@#2 &]
share|improve this question
up vote 3 down vote accepted

No brilliance here, but on my machine the following function is 8 or 9 times faster thancnt[k,n].

DistinctPrimes[k_, n_] :=
   Block[{r=Range[n]}, Length[Pick[r, Map[Length,FactorInteger[r]], k]]]
share|improve this answer

It appears that you are making this far more complicated than it needs to be. Look at Count. KennyColnago is wise to use listability, and to my surprise his use of FactorInteger is faster than PrimeNu at least in version 7. Here are two functions to compare:

f1[k_, n_] := Count[PrimeNu @ Range @ n, k]
f2[k_, n_] := Count[Length /@ FactorInteger @ Range @ n, k]

In version 7:

f1[6, 150000] // Timing
f2[6, 150000] // Timing
{1.544, 64}

{0.281, 64}
share|improve this answer
It is actually not the speed I am after (though it would be nice) - my goal is to find dpf for very large numbers. – martin Dec 19 '13 at 10:20
@martin Sorry, I missed that. How large is "very large" and you willing to wait a long time for very large numbers? – Mr.Wizard Dec 19 '13 at 10:33
Somewhere in the range 10^40 would be nice - but as large as poss, really :) Don't mind waiting, but only running on Windows 32-bit platform. – martin Dec 19 '13 at 14:56
@martin Oh dear; this method will never scale to that degree. I hope someone with greater knowledge has a more clever approach for you. – Mr.Wizard Dec 19 '13 at 15:00
Just to confirm:FactorInteger is faster than PrimeNu in version 9 as well, which makes no sense to me... – KennyColnago Dec 19 '13 at 16:58

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.