Return to Revisions

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.
 >>> num_common_factors(10, 25)
 2
 """
 # ... 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.

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.
 >>> num_common_factors(10, 25)
 2
 """
 return num_divisors(gcd(a, b))

and 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 can be done more concisely 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