def euler_totient(n):
    result = n
    p = 2
    while p * p <= n:
        # Check if p is a prime factor
        if n % p == 0:
            # If yes, then update n and result
            while n % p == 0:
                n //= p
            result -= result // p
        p += 1
    # If n is a prime number greater than 2
    if n > 1:
        result -= result // n
    return result
 
# Example usage
n = 10
print(f"Euler's totient function of {n} is: {euler_totient(n)}")

ZGVmIGV1bGVyX3RvdGllbnQobik6CiAgICByZXN1bHQgPSBuCiAgICBwID0gMgogICAgd2hpbGUgcCAqIHAgPD0gbjoKICAgICAgICAjIENoZWNrIGlmIHAgaXMgYSBwcmltZSBmYWN0b3IKICAgICAgICBpZiBuICUgcCA9PSAwOgogICAgICAgICAgICAjIElmIHllcywgdGhlbiB1cGRhdGUgbiBhbmQgcmVzdWx0CiAgICAgICAgICAgIHdoaWxlIG4gJSBwID09IDA6CiAgICAgICAgICAgICAgICBuIC8vPSBwCiAgICAgICAgICAgIHJlc3VsdCAtPSByZXN1bHQgLy8gcAogICAgICAgIHAgKz0gMQogICAgIyBJZiBuIGlzIGEgcHJpbWUgbnVtYmVyIGdyZWF0ZXIgdGhhbiAyCiAgICBpZiBuID4gMToKICAgICAgICByZXN1bHQgLT0gcmVzdWx0IC8vIG4KICAgIHJldHVybiByZXN1bHQKCiMgRXhhbXBsZSB1c2FnZQpuID0gMTAKcHJpbnQoZiJFdWxlcidzIHRvdGllbnQgZnVuY3Rpb24gb2Yge259IGlzOiB7ZXVsZXJfdG90aWVudChuKX0iKQ==