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.


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

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 :slight_smile: