让用户提供一个正整数 n。编写一个程序,输出小于 n 的 zp 的数量。
一个 zp 是指与 n 的最大公除数等于 1 的素数。
例如,n=6 的 zp 数是 1,因为有一个小于 6 的素数,即(5),其与6的最大公约数等于
1。
例如:
输入1
输出0
输入9
输出3
让用户提供一个正整数 n。编写一个程序,输出小于 n 的 zp 的数量。
一个 zp 是指与 n 的最大公除数等于 1 的素数。
例如,n=6 的 zp 数是 1,因为有一个小于 6 的素数,即(5),其与6的最大公约数等于
1。
例如:
输入1
输出0
输入9
输出3
该回答引用ChatGPT
代码解释:
gcd 函数用于求两个数的最大公约数。
is_prime 函数用于判断一个数是否为质数。
count_zp 函数用于统计小于 n 的 zp 的数量,遍历 1 到 n-1 的所有数,判断是否和 n 的最大公约数为 1 并且是否为质数,如果是,则 zp 的数量加 1。
n 为用户输入的正整数。
最后输出小于 n 的 zp 的数量。
def gcd(a, b):
# 求最大公约数
while b:
a, b = b, a % b
return a
def count_zp(n):
# 判断是否为质数
def is_prime(x):
if x < 2:
return False
for i in range(2, int(x**0.5)+1):
if x % i == 0:
return False
return True
# 统计 zp 的数量
count = 0
for i in range(1, n):
if gcd(i, n) == 1 and is_prime(i):
count += 1
return count
n = int(input("请输入一个正整数:"))
print(f"小于{n}的zp数量为:{count_zp(n)}")