时间戳

首页 > 解决方案 > 如何找到GCD等于1并且这些数字小于python中给出的数字

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

问题描述

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

a是输入数字并且b是小于输入一且不等于零的列表数字。然后打印出来。

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

我是初学者。

标签： pythonpython-3.xmathgreatest-common-divisor

解决方案

关于您的代码的一些评论：

  • 您应该始终将这样的代码封装在一个函数中；编写一个函数find_coprimes，它接受一个参数n并返回你想要的列表；
  • 为了测试你的函数的正确性，写一个引用函数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-loop 在 -loop 内重复执行for；每当有这样的嵌套循环时，您必须确保变量在外部循环开始时按照您希望它们的方式重新初始化；在您的情况下，变量a在 -loop 内被修改while，因此，它的值在for-loop 的下一次迭代开始时是错误的。
  • break-loop末尾的语句没有while意义；一般来说，break语句只有被封装在if条件中才有意义，并且它们充当循环条件的替代品；但是总是可以在不使用的情况下编写循环break，我建议你完全忘记break。
  • q使用and执行 gcd 计算后r，您的代码缺少一些东西来告诉它是否保留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修改副本。

进一步封装

注意 functionfind_coprimes_ref比 function 更容易阅读find_coprimes吗？这不仅仅是因为我们使用了库函数math.gcd。这是因为库函数math.gcd是一个干净封装的函数，其名称清楚地解释了它的作用。您的代码在 for 循环中包含一个 while 循环，并且很难跟踪每个变量和正在发生的所有事情，并且不会丢失我们的子目标和总体目标。

为了使您的函数更易于阅读、更易于编码和更易于调试，您应该将 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)

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

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

推荐阅读