Kiểm tra xem một số có phải là Số Trojan trong Python hay không

Giả sử chúng ta có một số n, chúng ta phải kiểm tra xem n có phải là Số Trojan hay không. Như chúng ta biết rằng Số Trojan là một con số mạnh mẽ mà không có sức mạnh hoàn hảo. Số n là một số mạnh khi với mọi ước nguyên tố hoặc thừa số p của n, p ^ 2 cũng là một ước. Nói cách khác, mọi thừa số nguyên tố đều xuất hiện ít nhất hai lần. Số lượng Trojan rất mạnh. Nhưng điều ngược lại là không đúng. Vì vậy, nó có nghĩa là, không phải tất cả các số mạnh đều là số Trojan:chỉ những số không thể được biểu diễn dưới dạng a ^ b.

Vì vậy, nếu đầu vào là 72, thì đầu ra sẽ là Đúng, vì 72 có thể được biểu diễn dưới dạng (6 * 6 * 2) =(6 ^ 2 * 2). Số mạnh nhưng không có sức mạnh hoàn hảo.

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

• Xác định một hàm check_perfect_pow (). Điều này sẽ mất n
• nếu n giống 1, thì
  • trả về True
• đối với x trong phạm vi 2 đến phần nguyên của (căn bậc hai của n) + 1, thực hiện
  • y:=2
  • p =x ^ y
  • while p <=n và p> 0, do
    • nếu p giống n, thì
      • trả về True
    • y:=y + 1
    • p =x ^ y
• trả về Sai
• Xác định một hàm check_strong_num (). Điều này sẽ mất n
• count:=một bản đồ để lưu giữ tần suất của các con số, ban đầu tất cả đều là 0
• trong khi n mod 2 giống 0, hãy thực hiện
  • n:=n / 2 (phép chia số nguyên)
  • count [2]:=count [2] + 1
• đối với tôi trong phạm vi 3 đến phần nguyên của (căn bậc hai của n) + 1, tăng 2, thực hiện
  • trong khi n mod, tôi giống với 0, hãy thực hiện
    • n:=n / i (phép chia số nguyên)
    • count [i]:=count [i] + 1
• nếu n> 2 khác 0, thì
  • count [n]:=count [n] + 1
• cờ:=0
• đối với mỗi khóa, giá trị trong các mục () của số lượng, thực hiện
  • nếu giá trị bằng 1, thì
    • cờ:=1
    • break
• nếu cờ giống 1, thì
  • trả về Sai
• trả về True
• Từ phương thức chính, hãy làm như sau -
  • trả về true khi check_perfect_pow (n) là False và check_strong_num (n) là true, nếu không thì trả về false

Ví dụ

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

from math import sqrt, pow
def check_perfect_pow(n):
   if n == 1:
      return True
   for x in range(2, int(sqrt(n)) + 1):
      y = 2
      p = x**y
      while p <= n and p > 0:
         if p == n:
            return True
         y += 1
         p = x**y
   return False
def check_strong_num(n):
   count = {i:0 for i in range(n)}
   while n % 2 == 0:
      n = n // 2
      count[2] += 1
   for i in range(3,int(sqrt(n)) + 1, 2):
      while n % i == 0:
         n = n // i
         count[i] += 1
   if n > 2:
      count[n] += 1
   flag = 0
   for key,value in count.items():
      if value == 1:
         flag = 1
         break
   if flag == 1:
      return False
   return True
def isTrojan(n):
   return check_perfect_pow(n) == False and check_strong_num(n)
n = 72
print(isTrojan(n))

Đầu vào

72

Đầu ra

True