Chương trình đếm số lượng phép toán tối thiểu cần thiết để tạo các số không phải là nguyên tố trong Python?

Giả sử chúng ta có hai số A và B. Bây giờ trong mỗi phép toán, chúng ta có thể chọn bất kỳ một số nào trong số đó và tăng nó lên 1 hoặc giảm nó đi 1. Chúng ta phải tìm số phép toán nhỏ nhất mà chúng ta cần sao cho ước số chung lớn nhất giữa A và B không phải là 1.

Vì vậy, nếu đầu vào là A =8, B =9, thì đầu ra sẽ là 1, vì chúng ta có thể chọn 9 rồi tăng nó lên 10, vì vậy 8 và 10 không phải là nguyên tố.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau:

• nếu gcd của a và b không giống 1 thì

  • trả về 0

• nếu a chẵn hoặc b chẵn thì

  • trả lại 1

• nếu không,

  • nếu gcd của a + 1 và b không giống với 1 hoặc gcd của a - 1 và b không giống với 1 hoặc gcd của a và b - 1 không giống với 1 hoặc gcd của a và b + 1 không giống với 1, sau đó

    • trả lại 1

  • nếu không,

    • trả về 2

Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn

Ví dụ

from math import gcd

class Solution:
   def solve(self, a, b):
      if gcd(a, b) != 1:
         return 0
      if a % 2 == 0 or b % 2 == 0:
         return 1
      else:
         if (gcd(a + 1, b) != 1 or gcd(a - 1, b) != 1 or gcd(a, b - 1) != 1 or gcd(a, b + 1) != 1):
            return 1
      else:
         return 2

ob = Solution()
A = 8
B = 9
print(ob.solve(A, B))

Đầu vào

8,9

Đầu ra

1