View Single Post
Old 2020-02-14, 09:49   #5
axn
 
axn's Avatar
 
Jun 2003

24×5×59 Posts
Default

A faster version using inclusion/exclusion principle rather than recursion:
Code:
howmanyfactors(n)=#factor(n)[,1];
getnum(n)=my(s=0, z); for(i=2,log(n)/log(2), if(!issquarefree(i), next()); z=floor(n^(1/i))-1; if(howmanyfactors(i)%2==0, s-=z, s+=z)); s
EDIT:- Apparently I reinvented Möbius function

Last fiddled with by axn on 2020-02-14 at 10:15
axn is offline   Reply With Quote