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

```
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.

that’s a shame thank’s