Numbers which divide a number

TrustyTony 1 849 Views

Here another small snippet of mathematical nature returning all possible divisors of number.
(set is, by the way, needed because of perfect squares

Not possible to edit the snippet part but here the same with less stupid command line interface (not repeating the loop):

def divides(n):
    return sorted(set(sum( ([x,n/x] for x in range(1, int(n**0.5+0.5) + 1) if not n%x), [] )))

if __name__ =='__main__':
    import sys
    
    sequence = map(int, sys.argv[1:]) if sys.argv[1:] else (45, 53, 64,1231435)
    for number in sequence:
        print( "%s divides %i " %
              (', '.join(map(str, divides(number))), number) )

Without set:

def divides(n):
    return sorted(sum( ([x,n/x] if x*x != n else [x] for x in range(1, int(n**0.5+0.5) + 1) if not n%x), [] ))

if __name__ =='__main__':
    import sys
    
    sequence = map(int, sys.argv[1:]) if sys.argv[1:] else (45, 53, 64,1231435)
    for number in sequence:
        print( "%s divides %i " %
              (', '.join(map(str, divides(number))), number) )
def divides(n):
    return sorted(set(sum( ([x,n/x] for x in range(1, int(n**0.5+0.5) + 1) if not n%x), [] )))

if __name__ =='__main__':
    import sys
    if sys.argv[1:]:
        for number in map(int, sys.argv[1:]):
            print( "%s divides %i " %
                  (', '.join(map(str, divides(number))), number) )
    else:
        for number in (45, 53, 64,1231435):
            print( "%s divides %i " %
                  (', '.join(map(str, divides(number))), number) )
Member Avatar for TrustyTony
TrustyTony 888 pyMod

Finally same without sort and as memory saving generator:

import sys
    
def divides_gen(number):
    high = []
    sqr = int(number ** 0.5)
    for divisor in xrange(1, sqr, 1+ (number & 1)):
        if not number%divisor:
            yield divisor
            high.append(number//divisor)
    if sqr*sqr== number: yield sqr
    for divisor in reversed(high):
        yield divisor

if __name__ =='__main__':
    sequence = map(int, sys.argv[1:]) if sys.argv[1:] else (45, 53, 64,1231435)
    for number in sequence:
        print( "%s divides %i " %
              (', '.join(str(divisor) for divisor in divides_gen(number)),
               number) )
Edited by TrustyTony because: n/a
Member Avatar for TrustyTony
TrustyTony 888 pyMod

And one step more optimized odd/even:

from __future__ import print_function
import sys
    
def divides_gen(number):
    high = [number]
    sqr = int(number ** 0.5)
    yield 1
    for divisor in xrange(3, sqr, 2) if (number & 1) else xrange(2, sqr, 2):
        if not number%divisor:
            yield divisor
            high.append(number//divisor)
    if sqr*sqr== number: yield sqr
    for divisor in reversed(high):
        yield divisor

if __name__ =='__main__':
    sequence = map(int, sys.argv[1:]) if sys.argv[1:] else (45, 53, 64,12345678987654321)
    for number in sequence:
        for divisor in divides_gen(number):
            print(divisor, end=', ')

        print("divides", number)

Notice alternative values if for ranges, it is very handy sometimes!

EDIT: more responsive for loop print instead of join.

Edited by TrustyTony because: n/a
Member Avatar for Gribouillis
Gribouillis 1,391 Programming Explorer

Notice that

>>> 111111111**2 == 12345678987654321
True
Member Avatar for TrustyTony
TrustyTony 888 pyMod

Gribouillis: Perfect square is taken care by line 12 of my last code, here even little changed version:

if sqr*sqr== number: yield sqr
J:\test>divisors 12345678987654321
1, 3, 9, 27, 37, 81, 111, 333, 999, 1369, 2997, 4107, 12321, 36963, 110889, 333667, 1001001, 3003003
, 9009009, 12345679, 27027027, 37037037, [B]111111111[/B], 333333333, 456790123, 999999999, 1370370369, 411
1111107, 12333333321, 36999999963, 111333666889, 334001000667, 1002003002001, 3006009006003, 4119345
674893, 9018027018009, 12358037024679, 37074111074037, 111222333222111, 152415789971041, 33366699966
6333, 457247369913123, 1371742109739369, 4115226329218107, 12345678987654321  divides 12345678987654
321

Did one of the versions fail in it? 64 is test case for that: 8*8 =64. The other versions though complained number too big to convert to int.

This program is of course slow for biggest numbers, but it would be also slow to multiply from permutations of prime factors (maybe faster with biggest ones, but so what).

Also this code has benefit of not being directly factoring, which one question deals with, that is why I did not yet want to send my factoring function before he finish. If he is clever, he can catch some idea from this.

from __future__ import print_function
import sys
    
def divides_gen(number):
    high = [number]
    sqr = int(number ** 0.5)
    yield 1
    for divisor in xrange(3, sqr, 2) if (number & 1) else xrange(2, sqr, 2):
        if not number%divisor:
            yield divisor
            high.append(number//divisor)
    if sqr*sqr== number:
         yield sqr
    for divisor in reversed(high):
        yield divisor

if __name__ =='__main__':
    sequence = map(int, sys.argv[1:]) if sys.argv[1:] else (45, 53, 64, 12345678987654321)
    for number in sequence:
        pad = '%%%is' % (len(str(number))+3)
        for divisor in divides_gen(number):
            print(pad % divisor, end=',')
        print("\b divides", number)
        print('\n','-'*60)
Edited by TrustyTony because: n/a
Member Avatar for TrustyTony
TrustyTony 888 pyMod

Oh, I got it. It was not the perfect square, but the fact that odd number 3 is factor of even number 6. So we can only optimize the even numbers, like I did until I got carried away.

Also must go until sqr if number is not perfect square (6).

from __future__ import print_function
import sys
    
def divides_gen(number):
    high = [number]
    sqr = int(number ** 0.5)
    limit = sqr+(sqr*sqr != number)
    yield 1
    for divisor in xrange(3, limit, 2) if (number & 1) else xrange(2, limit):
        if not number%divisor:
            yield divisor
            high.append(number//divisor)
    if sqr*sqr== number: yield sqr
    for divisor in reversed(high):
        yield divisor

if __name__ =='__main__':
    sequence = map(int, sys.argv[1:]) if sys.argv[1:] else (6, 45, 53, 64, 123456, 12345678987654321)
    for number in sequence:
        for divisor in divides_gen(number):
            print(divisor, end=', ')

        print("\b\b divides", number)
Edited by TrustyTony because: n/a
Member Avatar for TrustyTony
TrustyTony 888 pyMod

Not so bad timing from my function, only problem is that can not wait to get comparable results (without loop my time is 0.0 seconds):

from sympy.ntheory import divisors
print 'divisors',divisors
from divi import divides
print 'divides', divides
import time
import random
test_no = 10
rands = list(random.randint(1E5,1E6) for _ in xrange(test_no))
results = []
for divi in (divides, divisors):
    print divi
    for number in rands:
        t0 = time.time()
        for i in range(1000):
            this = list(divi(number))
        t1 = time.time()
        results.append((this,t1-t0))
        print number, this, (t1-t0)*1000
    print divi, 'Finished'
    print 'Time: %.1f us' % (1000 * sum(ti for res,ti in results[-100:]))
    print '-'*60

for symres, myres in zip(results[:test_no], results[test_no:]):
    if not set(symres[0]) == set(myres[0]):
        print symres, myres, 'do not match'
        break
else:
    print 'Check passed'

print 'my time: %.1f us' % (1000 * sum(ti for res,ti in results[100:]))
print 'sympy time: %.1f us' % (1000 * sum(ti for res,ti in results[:100]))
print 'Difference: %i %%' % (100- 100*(sum(ti for res,ti in results[:100])/
                                 sum(ti for res,ti in results[100:])))
divisors <function divisors at 0x01010EF0>
divides <function divides at 0x01376670>
<function divides at 0x01376670>
261534 [1, 2, 3, 6, 7, 13, 14, 21, 26, 39, 42, 78, 91, 182, 273, 479, 546, 958, 1437, 2874, 3353, 62
27, 6706, 10059, 12454, 18681, 20118, 37362, 43589, 87178, 130767, 261534] 140.000104904
360106 [1, 2, 180053, 360106] 157.00006485
831819 [1, 3, 277273, 831819] 125.0
683872 [1, 2, 4, 7, 8, 14, 16, 28, 32, 43, 56, 71, 86, 112, 142, 172, 224, 284, 301, 344, 497, 568,
602, 688, 994, 1136, 1204, 1376, 1988, 2272, 2408, 3053, 3976, 4816, 6106, 7952, 9632, 12212, 15904,
 21371, 24424, 42742, 48848, 85484, 97696, 170968, 341936, 683872] 217.99993515
220606 [1, 2, 73, 146, 1511, 3022, 110303, 220606] 125.0
859932 [1, 2, 3, 4, 6, 9, 12, 18, 36, 23887, 47774, 71661, 95548, 143322, 214983, 286644, 429966, 85
9932] 233.999967575
249582 [1, 2, 3, 6, 41597, 83194, 124791, 249582] 125.0
969012 [1, 2, 3, 4, 6, 9, 11, 12, 18, 22, 33, 36, 44, 66, 99, 132, 198, 396, 2447, 4894, 7341, 9788,
 14682, 22023, 26917, 29364, 44046, 53834, 80751, 88092, 107668, 161502, 242253, 323004, 484506, 969
012] 264.999866486
375790 [1, 2, 5, 10, 37579, 75158, 187895, 375790] 157.00006485
471998 [1, 2, 19, 38, 12421, 24842, 235999, 471998] 187.00003624
<function divides at 0x01376670> Finished
Time: 1733.0 us
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

Edit Preview