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