真题精讲：两道考级风格题讲透

# 真题精讲：两道 GESP 5 级风格题（原创类真题）

# 题一：互质伙伴统计——1~n 中有多少个数与 n 互质
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

def count_coprime(n):
    cnt = 0
    for x in range(1, n + 1):
        if gcd(x, n) == 1:
            cnt = cnt + 1
    return cnt

print("1~12 中与 12 互质的有", count_coprime(12), "个")
print("1~30 中与 30 互质的有", count_coprime(30), "个")

print("——————")

# 题二：第 k 个质数——先撒小网，不够就翻倍，再筛法点名
def kth_prime(k):
    limit = 100
    while True:
        is_p = [True] * (limit + 1)
        is_p[0] = is_p[1] = False
        for i in range(2, limit + 1):
            if is_p[i]:
                for j in range(i * i, limit + 1, i):
                    is_p[j] = False
        primes = [x for x in range(2, limit + 1) if is_p[x]]
        if len(primes) >= k:
            return primes[k - 1]
        limit = limit * 2    # 网里的质数不够，就把网撒大一倍

print("第 10 个质数是", kth_prime(10))
print("第 100 个质数是", kth_prime(100))
print("第 1000 个质数是", kth_prime(1000))