Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
1000000

output:
400000
"""

import sys


def gcd(x, y):
    if x < y:
        x, y = y, x

    while y > 0:
        r = x % y
        x = y
        y = r

    return x


def phi(n):
    ans = 0

    for k in range(1, n + 1):
        if gcd(n, k) == 1:
            ans += 1

    return ans


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    n1 = int(_input[0])
    print(phi(n1))

Fixed submission:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
1000000

output:
400000
"""

import sys


def min_prime_factor(n):
    k = 2
    while True:
        if pow(k, 2) > n:
            return n
        if not n % k:
            return k
        k += 1


def phi(n):
    ans = n
    while True:
        p = min_prime_factor(n)
        if n == 1:
            break
        while not n % p:
            n //= p
        ans *= (1 - 1 / p)
    return int(ans)


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    n1 = int(_input[0])
    print(phi(n1))

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
1000000

output:
400000
"""

import sys


def is_prime(n):
    if n == 2:
        return True
    elif n < 2 or not n % 2:
        return False

    return pow(2, n - 1, n) == 1


def phi(n):
    y = n
    for k in range(2, n + 1):
        if not n % k and is_prime(k):
            y -= y / k
    return int(y)


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    n1 = int(_input[0])
    print(phi(n1))

Fixed submission:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
1000000

output:
400000
"""

import sys


def min_prime_factor(n):
    k = 2
    while True:
        if pow(k, 2) > n:
            return n
        if not n % k:
            return k
        k += 1


def phi(n):
    ans = n
    while True:
        p = min_prime_factor(n)
        if n == 1:
            break
        while not n % p:
            n //= p
        ans *= (1 - 1 / p)
    return int(ans)


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    n1 = int(_input[0])
    print(phi(n1))

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
1000000

output:
400000
"""

import sys
import math


def is_prime(n):
    if n == 2:
        return True
    elif n < 2 or not n % 2:
        return False

    k = 3
    while k <= math.sqrt(n):
        if not n % k:
            return False
        k += 2

    return True


def phi(n):
    y = n
    for k in range(2, n + 1):
        if not n % k and is_prime(k):
            y -= y / k
    return int(y)


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    n1 = int(_input[0])
    print(phi(n1))

Fixed submission:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
1000000

output:
400000
"""

import sys


def min_prime_factor(n):
    k = 2
    while True:
        if pow(k, 2) > n:
            return n
        if not n % k:
            return k
        k += 1


def phi(n):
    ans = n
    while True:
        p = min_prime_factor(n)
        if n == 1:
            break
        while not n % p:
            n //= p
        ans *= (1 - 1 / p)
    return int(ans)


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    n1 = int(_input[0])
    print(phi(n1))

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
1000000

output:
400000
"""

import sys


def is_prime(n):
    if n == 2:
        return True
    elif n < 2 or not n % 2:
        return False

    return pow(2, n - 1, n) == 1


def min_prime_factor(n):
    if is_prime(n):
        return n
    else:
        k = 2
        while True:
            if not n % k:
                break
            k += 1
    return k


def phi(n):
    ans = n
    while True:
        p = min_prime_factor(n)
        if n == 1:
            break
        while n % p == 0:
            # print(n, p)
            n //= p
        ans *= (1 - 1 / p)
    return int(ans)


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    n1 = int(_input[0])
    print(phi(n1))

Fixed submission:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
1000000

output:
400000
"""

import sys


def min_prime_factor(n):
    k = 2
    while True:
        if pow(k, 2) > n:
            return n
        if not n % k:
            return k
        k += 1


def phi(n):
    ans = n
    while True:
        p = min_prime_factor(n)
        if n == 1:
            break
        while not n % p:
            n //= p
        ans *= (1 - 1 / p)
    return int(ans)


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    n1 = int(_input[0])
    print(phi(n1))