如何找到 GCD 等于 1 且这些数字小于 python 中给出的数字

Question

我正在尝试编写代码，为您提供小于给定或输入的数字，并且它们的 GCD 等于 1。我写了这段代码，但我不知道是否有效或为什么无效。例如，我选择了数字 6。数组将类似于 [1,2,3,4,5]。我的意思是过滤 GCD 等于 1 的数字。所以它将是 [1,5]。他们的数量是两个。

a为输入的数字，b为小于输入的1且不为0的列表数字。然后打印出来。

a = int(input("enter number \n"))
b = list(range(1,a))
print (b)

然后我将列表转换为数组

for i in range(1, len(b)):
        b[i] = int(b[i])

然后这个

        r = a % b[i]

        q = int ( a / b[i])

        while(r!=0):
            
            a = b[i]

            b[i] = r

            q = int ( a / b[i])

            r = a - (b[i] * q)


            print ( a , b[i], r )
            break

我是初学者。

Answer 1

关于您的代码的几点评论：

您应该始终将这样的代码封装在一个函数中；编写一个函数 find_coprimes，它接受一个参数 n 和 returns 你想要的列表；
为了测试你函数的正确性，写一个参考函数find_coprimes_ref做同样的事情，但是使用库函数来确保没有错误；这会教你寻找相关的库函数，你可以比较两个函数的结果；
初始循环for i in range(1, len(b)): b[i] = int(b[i])是错误的有两个原因； 1) 它没有效果，因为 b 已经是一个整数列表。 2) 列表是 0 索引的，因此 b 的每个元素的正确迭代将是 for i in range(0, len(b)): 或简单地 for i in range(len(b)):;
您的代码有两个嵌套循环：一个 while 循环在 for 循环内重复执行；每当有这样的嵌套循环时，您必须确保在外部循环开始时按照您希望的方式重新初始化变量；在你的例子中，变量 a 在 while 循环内被修改，因此，它的值在 for 循环的下一次迭代开始时是错误的。
while 循环末尾的 break 语句没有意义；通常，break 语句仅在封装在 if 条件中时才有意义，并且它们充当循环条件的替代品；但是总是可以在不使用 break 的情况下编写循环，我建议您完全忘记 break。
在使用 q 和 r 执行 gcd 计算后，您的代码缺少一些东西来告诉它是否在最终结果中保留 b[i]；
对于python中的整数除法，最好使用//而不是int(... / ...)。

代码

import math

def find_coprimes_ref(n):
  return [x for x in range(1,n) if math.gcd(x,n) == 1]

def find_coprimes(n):
  result = []
  for x in range(1, n):
    a = n
    b = x
    r = a % b
    q = a // b
    while (r > 1):
      a = b
      b = r
      q = a // b
      r = a - b * q
    if (r == 1):
      result.append(x)
  return result

# TESTING

for n in range(1, 31):
  coprimes_ref = find_coprimes_ref(n)
  coprimes = find_coprimes(n)
  if coprimes_ref != coprimes:
    print(n, coprimes_ref, coprimes)

请注意我的代码如何在循环中从不修改 n 或 x；相反，我制作了名为 a 和 b 的副本并修改了副本。

进一步封装

请注意函数 find_coprimes_ref 为何比函数 find_coprimes 更易读？这不仅仅是因为我们使用了库函数math.gcd。这是因为库函数 math.gcd 是一个干净封装的函数，其名称可以清楚地解释它的作用。您的代码在 for 循环中包含一个 while 循环，很难跟踪每个变量和正在发生的一切，并且不会忘记我们的子 objective 和整体 objective.

为了使您的函数更易于阅读、编码和调试，您应该将 gcd 计算封装在一个名为 gcd:

的函数中

def gcd(a, b):
  r = a % b
  q = a // b
  while (r > 1):
    a = b
    b = r
    q = a // b
    r = a - b * q
  return r

def find_coprimes(n):
  result = []
  for x in range(1, n):
    if gcd(a, b) == 1:
      result.append(x)
  return result

# TESTING GCD

for b in range(1, 31):
  for a in range(b, 31):
    r1 = math.gcd(a, b)
    r2 = gcd(a, b)
    if r1 != r2:
      print(a, b, r1, r2)

# TESTING FIND_COPRIMES

for n in range(1, 31):
  coprimes_ref = find_coprimes_ref(n)
  coprimes = find_coprimes(n)
  if coprimes_ref != coprimes:
    print(n, coprimes_ref, coprimes)

现在代码更容易调试的原因有两个：

gcd 和 find_coprimes 的逻辑完全分开，这意味着您可以清楚地推理出 gcd，而不会有弄乱列表和其中使用的其他变量的风险find_coprimes;
您可以分别测试您的功能 gcd 和您的功能 find_coprimes；如果某些地方不能正常工作，您将更准确地知道在哪里寻找问题，而不是仅仅思考“好吧，代码中某处有问题，但我不知道在哪里”。

Answer 2

您的代码中存在一些错误，例如 while 循环中的 break。我重构了您的代码，还添加了内置 math.gcd 函数来比较结果。

import math

def math_inbuilt_gcd(a, b):
    gcd_one = []
    for x in b:
        if math.gcd(x, a) == 1:
            gcd_one.append(x)
    print("gcd_one_math_fun:", gcd_one)


def gcd_my_fun(a, b):
    gcd_arr = []
    for i in range(len(b)):
        x, y = a, b[i] # taking x, y just to make things clear
        r = x % y # remainder
        q = int(x / y) # quotient

    while(r != 0):
        x = y
        y = r
        q = int(x/y)
        r = x % y

    if y == 1:
        gcd_arr.append(b[i])

    print("gcd_one_my_fun:", gcd_arr)


a = int(input("Enter number: "))
b = list(range(1, a))
print("b:", b)

math_inbuilt_gcd(a, b)
gcd_my_fun(a, b)

输出：

Enter number: 10
b: [1, 2, 3, 4, 5, 6, 7, 8, 9]
gcd_one_math_fun: [1, 3, 7, 9]
gcd_one_my_fun: [1, 3, 7, 9]

如何找到 GCD 等于 1 且这些数字小于 python 中给出的数字

How to find numbers which GCD equal to 1 and those numbers are less than given in python

python

python-3.x

math

greatest-common-divisor

代码

进一步封装