Count common factors

Question

I have written some code for calculating a count of common factors. Please help me remove anything unnecessary and shorten it.

Please tell me if any function in Python 3 can calculate common factors directly!

# a string of 2 numbers
# is input e.g. '10 15'
a,b=str(input()).split(' ')
a,b=int(a),int(b)
n=0
if a>=b:
 lim=a
else:
 lim=b
for num in range(1,lim):
 if a%num==0 and b%num==0:
 n+=1
print(n)

• Peilonrayz: Why does this have a VTC for lacking a description. Do you, the closer, not know what common factors are?

Answer 1

Coding style

There is a well-established coding style for Python, the PEP8 coding style, and conformance to that style can be checked online at PEP8 online.

In your case it reports "missing space around operator" in almost every code line. Fixing those issues increases the legibility of your code.

Program structure

It is better to separate the I/O from the actual computation. With a function to compute the number of common divisors you make your code more readable and reusable. In addition you can document each function and add test cases easily.

A check for main allows to run the script directly, or import it as a module.

So the overall program structure should be

def num_common_factors(a, b):
 """ Return the number of common factors of a and b. """
 # ... TODO ...
if __name__ == "__main__":
 a, b = map(int, input().split())
 print(num_common_factors(a, b))

Note also that reading the input line and the mapping to integers can be combined into a single statement.

Simplify (and fix) your code

Your solution is the "brute-force" approach: Test every possible number (in a suitable range) if it is a divisor of both numbers. That can be improved considerably (see below), but let's first discuss how your solution can simplified. First, the limit can be computed using the built-in min() function:

lim = min(a, b)

Then note that a range() excludes the upper bound, so you probably want

for num in range(1, lim + 1):

I would also avoid abbreviations, i.e. limit instead of lim. Finally the code can be written more concisely by summing a generator expression:

def num_common_factors(a, b):
 """ Return the number of common factors of a and b. """
 limit = min(a, b)
 return sum(1 for i in range(1, limit + 1) if a % i == 0 and b % i == 0)

Mathematics helps!

The problem can be solved more efficiently using some maths. Every common divisor of a and b is a divisor of the "greatest common divisor" of a and b, and vice versa. So the task can be split into two separate problems:

• Determine the greatest common divisor \$ g = \gcd(a, b) \$. This can be done efficiently using the Euclidian algorithm, but even better, Python has a built-in function math.gcd for that.
• Count the number of divisors of \$ g \$.

So our function would be

from math import gcd
def num_common_factors(a, b):
 """ Return the number of common factors of a and b.
 Example 1: 10 and 25 have the 2 common factors 1, 5.
 >>> num_common_factors(10, 25)
 2
 Example 2: 720 and 24 have the 8 common factors 1, 2, 3, 4, 6, 8, 12, 24.
 >>> num_common_factors(720, 24)
 8
 """
 g = gcd(a, b)
 return num_divisors(g)

where I also have added two test cases as examples.

Now we are left with the second task: counting the number of divisors. A simple implementation would be

def num_divisors(n):
 """Return the number of divisors of n."""
 count = 0
 for i in range(1, n+1):
 if n % i == 0:
 count += 1
 return count

which again can be done by summing a generator expression:

def num_divisors(n):
 """Return the number of divisors of n."""
 return sum(1 for i in range(1, n+1) if n % i == 0)

But this can be done far more efficiently using the prime number factorization: If $$ n = p_1^{e_1} ,円 p_2^{e_2} \cdots p_k^{e_k} $$ is the factorization of \$ n \$ into prime numbers \$ p_i \$ with exponents \$ e_i \$, then $$ \sigma_0(n) = (e_1+1)(e_2+1) \cdots (e_k+1) $$ is the number of divisors of \$ n \$, see for example Wikipedia: Divisor function. Example: $$ 720 = 2^4 \cdot 3^2 \cdot 5^1 \Longrightarrow \sigma_0(720) = (4+1)(2+1)(1+1) = 30 ,円 . $$

Here is a possible implementation (translated from the JavaScript here to Python):

def num_divisors(n):
 """Return the number of divisors of n."""
 count = 1 # Number of divisors
 factor = 2 # Candidate for prime factor of n
 # If n is not a prime number then it must have one factor
 # which is <= sqrt(n), so we try these first:
 while factor * factor <= n:
 if n % factor == 0:
 # factor is a prime factor of n, determine the exponent:
 exponent = 1
 n /= factor
 while n % factor == 0:
 exponent += 1
 n /= factor
 # factor^exponent is one term in the prime factorization of n,
 # this contributes as factor exponent + 1:
 count *= exponent + 1
 # Next possible prime factor:
 factor = 3 if factor == 2 else factor + 2
 # Now n is either 1 or a prime number. In the latter case,
 # it contributes a factor 2:
 if n > 1:
 count *= 2
 return count

Testing

As already mentioned above, test cases can be added to each function, and verified with the doctest module. Running the tests after each modification of the code helps to find programming errors.

We already added two test cases to the num_common_factors() function. Now we'll do this for the num_divisors() divisors function, which is essential to the program, and where a programming error can easily lead to wrong results.

One option is to compute a bunch of values using an alternative program and use the results as test cases. I chose PARI/GP to compute the number of divisors of \$ 1, \ldots, 20 \$, \$ 100, \ldots, 119\$, and \$ 10000, \ldots, 10019 \$:

? vector(20, n, numdiv(n))
%1 = [1, 2, 2, 3, 2, 4, 2, 4, 3, 4, 2, 6, 2, 4, 4, 5, 2, 6, 2, 6]
? vector(20, n, numdiv(99+n))
%2 = [9, 2, 8, 2, 8, 8, 4, 2, 12, 2, 8, 4, 10, 2, 8, 4, 6, 6, 4, 4]
? vector(20, n, numdiv(9999+n))
%3 = [25, 4, 8, 4, 12, 16, 4, 2, 24, 2, 32, 8, 6, 8, 8, 4, 12, 16, 4, 4]

and added these as test cases to the num_divisors() function:

def num_divisors(n):
 """Return the number of divisors of n.
 >>> [num_divisors(n) for n in range(1, 21)]
 [1, 2, 2, 3, 2, 4, 2, 4, 3, 4, 2, 6, 2, 4, 4, 5, 2, 6, 2, 6]
 >>> [num_divisors(n) for n in range(100, 120)]
 [9, 2, 8, 2, 8, 8, 4, 2, 12, 2, 8, 4, 10, 2, 8, 4, 6, 6, 4, 4]
 >>> [num_divisors(n) for n in range(10000, 10020)]
 [25, 4, 8, 4, 12, 16, 4, 2, 24, 2, 32, 8, 6, 8, 8, 4, 12, 16, 4, 4]
 """
 ... remaining function omitted ...

Testing is done by running

python -m doctest -v countcommonfactors.py 

on the command line (assuming that "countcommonfactors.py" is the name of your Python script).

• Utkarsh Sharma: Please tell me a bit about the map() function that you used in : a, b = map(int, input().split())
• Martin R: @UtkarshSharma: The first argument is a function, which is applied to every item in the second argument (which is an iterable). Documented here: docs.python.org/3/library/functions.html#map.
• Martin R: @UtkarshSharma: ... The result is an iterable, which is unpacked into a and b.
• Peilonrayz: Out of curiosity; is there a reason you don't remove if n % factor == 0: and the first n /= factor, and change exponent = 1 to exponent = 0?
• Martin R: @Peilonrayz: Then a multiplication count *= exponent + 1 would also be done if factor is not a divisor. That would work because exponent = 0 in that case. (The real reason is that I translated this back from a JavaScript with a repeat-while loop :)

Answer 2

So there's couple of things you can improve:

a,b=str(input()).split(' ')
a,b=int(a),int(b)
cdiv=[] #list to store common divisors
num=2
if(max(a,b)%min(a,b)==0): 
 c=min(a,b)
 for i in range(2,int(c**0.5)+1):
 while(c%i==0):
 cdiv.append(i)
 c/=i
 if(c>1): cdiv.append(c)
else:
 while(num<=min(a,b)//2):
 while(a % num==0)&(b % num==0):
 cdiv.append(num)
 a/=num
 b/=num
 num+=1

(1) you indeed should focus on prime divisors.

(2) maximal potential divisor of any number x is x//2 (floor from half of x), so it's enough to look for divisors until min(a,b)//2 (cause we are looking only for common divisors).

(3) some of the prime divisors could be multiple times divisors - so also you should look for these.

(4) after confirming single number being divisor you can divide both numbers by it - by decreasing the numbers you make it easier to take modulo from it next time (you could probably also do it if divisor is just divisor for one of the numbers, but then you would have to check both numbers separately, which I'm not sure is worth doing in terms of computational overhead).

• Werner Altewischer: You only have to iterate up to sqrt(min(a,b)) because if a or b is dividable by a number greater than its sqrt there also has to be a divider smaller than its sqrt.
• Martin R: @WernerAltewischer: That is not correct, see also my comment at your answer. 10 and 25 have the common factor 5, which is larger than sqrt(min(10, 25)).
• Georgina Skibinski: @Werner Altewischer - you're right in terms of finding divisors for a single number, but if we're talking about common divisors - you might be interested only in exactly this higher divisor. (10, 25) is a very good counter-example.
• Martin R: @GrzegorzSkibinski: Your solution seems to be problematic as well: 720 and 24 have the 8 common factors 1, 2, 3, 4, 6, 8, 12, 24, but your code produces [2, 2, 2].
• Georgina Skibinski: Thanks @Martin R I tweaked my answer - it's for the case when b%a==0

Answer 3

Basically you only need to iterate up to sqrt(a) because the inverse of every factor <= sqrt(a) gives you the one which is greater than sqrt(a).

See the following code example:

import math
def factors(a):
 ans = set()
 for i in range(1, int(math.sqrt(a)) + 1):
 if a % i == 0:
 ans.add(i)
 ans.add(a // i)
 return ans
def find_common_factors(a, b):
 factors_a = factors(a)
 factors_b = factors(b)
 return factors_a.intersection(factors_b)

• Martin R: I might be wrong, but there seems to be a problem with your solution. find_common_factors(10, 25) returns an empty list, but there are two common factors (1, 5).
• Martin R: Another example: 720 and 24 have 8 common factors, not 2.
• Werner Altewischer: you're right, max_prime should be int(max(math.sqrt(a), math.sqrt(b))). By the way, 1 is not considered a factor (it is implicit for all n)
• Martin R: 1 is not a prime factor of n, but is is a common factor of a and b (and the original code counts it as well). Btw, your find_common_factors(720, 24) misses the common factor 24.
• Martin R: Another problem: factors(20, ...) does not find the factor 4. factors(78, ...) does not find the factor 6.