3
$\begingroup$

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 &]
Improve this question
$\endgroup$

2 Answers 2

Reset to default
4
$\begingroup$

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]]]
Improve this answer
$\endgroup$
2
$\begingroup$

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}
Improve this answer
$\endgroup$
5
  • $\begingroup$ It is actually not the speed I am after (though it would be nice) - my goal is to find dpf for very large numbers. $\endgroup$
    – martin
    Dec 19, 2013 at 10:20
  • $\begingroup$ @martin Sorry, I missed that. How large is "very large" and you willing to wait a long time for very large numbers? $\endgroup$
    – Mr.Wizard
    Dec 19, 2013 at 10:33
  • $\begingroup$ 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. $\endgroup$
    – martin
    Dec 19, 2013 at 14:56
  • $\begingroup$ @martin Oh dear; this method will never scale to that degree. I hope someone with greater knowledge has a more clever approach for you. $\endgroup$
    – Mr.Wizard
    Dec 19, 2013 at 15:00
  • 3
    $\begingroup$ Just to confirm:FactorInteger is faster than PrimeNu in version 9 as well, which makes no sense to me... $\endgroup$
    – KennyColnago
    Dec 19, 2013 at 16:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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