Here is a cython version suitable only for ints.
from sage.rings.arith import divisors
from sage.rings.arith import is_prime
from sage.rings.integer cimport Integer
cpdef is_zk_cython(int n):
cdef list d
cdef int *m
cdef int i, wi, w, s
cdef Integer a = Integer(n)
if a.is_prime() : return False
d = a.divisors()
s = sum(d)
if s & 1: return False
s >>= 1
if s < a: return False
target = s - a
if target < 2 : return True
m = <int *>sage_malloc(n * sizeof(int))
m[0] = 0
for i in xrange(1, n): m[i] = 1
for i in xrange(1, len(d)):
wi = d[i]
if wi > target: break
for w in xrange(target, wi - 1, -1):
mw = m[w - wi] + wi
if mw > m[w]:
m[w] = mw
if m[target] == target:
sage_free(m)
return True
sage_free(m)
return False
> No need to call is_prime(a), divisors would only return length two;
> otherwise the sieving is done twice. (Unless Sage does something
> extra smart behind the scenes.)
it's not needed, but primality testing is much cheaper than factoring,
so it's an early abort.
#non prime case
sage: timeit('ZZ(123456789).is_prime()')
625 loops, best of 3: 5.15 µs per loop
sage: timeit('ZZ(123456789).divisors()')
625 loops, best of 3: 144 µs per loop
sage: timeit('ZZ(123456789).factor()')
625 loops, best of 3: 133 µs per loop
#prime case
sage: timeit('ZZ(123456791).is_prime()')
625 loops, best of 3: 3.1 µs per loop
sage: timeit('ZZ(123456791).divisors()')
625 loops, best of 3: 132 µs per loop
sage: timeit('ZZ(123456791).factor()')
625 loops, best of 3: 125 µs per loop
--
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to
sage-devel+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org
