# GCD common factor

there is a way to know how many common divisor are in a range without using GCD? it’s very long for big number

For example?

as exemple if i want know the prime candidate in a modulo i must do like 2* 3* 5* 7 = modulo 210

for knowing prime candidate in that range
i must do that

def gcd(a, b):
while b != 0:
a, b = b, a % b
return a
modulo = 210
candidates = [i for i in range(1, modulo) if gcd(i, modulo) == 1]

sorry for the tabulation

and it’s very long for big modulo. i need to know only how many they are, not necessary the list itself.
Event if i inc a variable it’s long, becose that’s try every number

as exemple for a modulo like
40729680599249024150621323470 it’s insane only knowing how many candidate

The “candidates” are called “totatives” and the number of candidates is called the Euler phi function.

Since your “modulo” is a product of distinct primes, the totient function is easy to compute. First, `φ(2 * 3 * 5 * 7)` is just the product `φ(2) * φ(3) * φ(5) * φ(7)`. Second, `φ(p)` where p is prime is just `p - 1`.

So, `φ(210) = φ(2⋅3⋅5⋅7) = φ(2)φ(3)φ(5)φ(7) = 1⋅2⋅4⋅6 = 48` which is the same as `len(candidates)` in your example.

2 Likes

thank’s for the function and the grammar you save me alot of time

``````totative = 2
phi = 1
for prime in primes[1:]:  #begin with primes 3
totative *= prime
phi *= prime - 1
``````

See the pinned topic for how to format code, and better use `for prime in primes:` instead of indices.

1 Like

that’s a shame thank’s