Revision history [back]

Hi,

Generating a long list takes time. If speed is an issue too, you could consider defining your own squarefree test.

sage: %cython
sage: cimport cython
sage: @cython.cdivision(True)
sage: #Fast up to 5*10^8
sage: cpdef bint is_csquarefree(long long n, unsigned long long priem=10**6):
...       cdef unsigned long p
...       cdef unsigned int* eerste=[2,3,5]
...       cdef unsigned int i=1,k
...       cdef unsigned int* diff=[6,4,2,4,2,4,6,2]     
...       if not n: return 0
...       if n<0: n=-n     
...       for k in xrange(3):
...           if not n%eerste[k]: 
...               n//=eerste[k]    #In 539 of 900 cases a number not dividable by 4,9,25
...               if not n%eerste[k]: return False
...      
...       p=7
...       while p<=priem and p*p<=n:
...           if not n%p: 
...               e=1 ; n//=p
...               if not n%p: return False
...               
...           p+=diff[i%8]
...           if not p%7: i+=1 ; p+=diff[i%8]                     #Small lost of time
...           i+=1       
...       return True

Test it:

sage: for k in xsrange(1,1000):
...       if is_csquarefree(k)!=is_squarefree(k): print k

Enjoy speed:

sage: timeit('for k in xrange(10^8,10^8+10^3): is_squarefree(k)==True')
sage: timeit('for k in xrange(10^8,10^8+10^3): is_csquarefree(k)==True')
25 loops, best of 3: 29.2 ms per loop
125 loops, best of 3: 4.86 ms per loop