Блог

Я пытаюсь написать код, который дает вам числа, которые меньше заданного или введенного числа, а их 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
 

Я новичок.

Несколько комментариев о вашем коде:

• Вы всегда должны инкапсулировать подобный код в функцию; напишите функцию 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, выполняемый многократно внутри цикла for -loop; всякий раз, когда есть такие вложенные циклы, вы должны убедиться, что переменные повторно инициализируются так, как вы предполагаете, в начале внешнего цикла; в вашем случае переменная a изменяется внутри цикла while -loop, ив результате его значение неверно в начале следующей итерации for цикла.
• break Оператор в конце цикла while -loop не имеет смысла; в общем, break операторы имеют смысл, только если они инкапсулированы в if условное выражение и действуют как замена условия цикла; но всегда можно писать циклы без использования break вообще, и я рекомендую вам break полностью забыть об этом.
• После выполнения вычисления gcd с использованием q и 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 и изменяю копии.

Инкапсуляция еще больше

Обратите внимание, насколько function find_coprimes_ref намного легче читать, чем function find_coprimes ? Это не только потому, что мы использовали библиотечную функцию math.gcd . Это потому, что библиотечная функция math.gcd — это чисто инкапсулированная функция с именем, которое четко объясняет, что она делает. Ваш код содержит цикл while внутри цикла for, и немного сложно отслеживать каждую переменную и все, что происходит, и не терять из виду нашу подзадачу и общую цель.

Чтобы вашу функцию было легче читать, легче кодировать и легче отлаживать, вы должны инкапсулировать вычисление 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)
 

Есть две причины, по которым код теперь легче отлаживать:

• Логика for gcd и for find_coprimes четко разделена, что означает, что вы можете gcd четко рассуждать без какого-либо риска испортить список и другие переменные, используемые в find_coprimes ;
• Вы можете протестировать отдельно свою функцию gcd и свою функцию find_coprimes ; и если что-то не работает правильно, вы будете более точно знать, где искать проблему, а не просто думать: «Ну, что-то не так где-то в коде, но я понятия не имею, где».

В вашем коде есть несколько ошибок, например, break внутри цикла while. Я переработал ваш код, а также добавил встроенную 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]