在 Python 中检查某个数字是否为特洛伊数

pythonserver side programmingprogramming更新于 2025/10/17 7:08:17

假设我们有一个数字 n，我们必须检查 n 是否为特洛伊数。众所周知，特洛伊数是一个没有完美幂的强数。当 n 的每个素因子或因子 p 中，p^2 也是除数时，数字 n 就是强数。换句话说，每个素因子至少出现两次。特洛伊数是强数。但反之则不然。所以这意味着，并非所有强数都是特洛伊数:只有那些不能表示为 a^b 的强数。

因此，如果输入是 72，则输出将为 True，因为 72 可以表示为 (6*6*2) = (6^2 * 2)。强数但没有完美的力量。

为了解决这个问题，我们将遵循以下步骤 −

定义一个函数 check_perfect_pow() 。这将需要 n
如果 n 与 1 相同，则
- 返回 True
对于 x 在 2 到 (n 的平方根) + 1 的整数部分范围内的情况，执行
- y := 2
- p = x^y
- 当 p <= n 且 p > 0，执行
  - 如果 p 与 n 相同，则
    - 返回 True
  - y := y + 1
  - p = x^y
返回 False
定义一个函数 check_strong_num() 。这将需要 n
count := 一个用于保存数字频率的映射，最初所有数字均为 0
当 n mod 2 与 0 相同时，执行
- n := n / 2(整数除法)
- count[2] := count[2] + 1
对于范围在 3 到 (n 的平方根) + 1 的整数部分的 i，增加 2，执行
- 当 n mod i 与 0 相同时，执行
  - n := n / i(整数除法)
  - count[i] := count[i] + 1
如果 n > 2 非零，则
- count[n] := count[n] + 1
flag := 0
对于 count 的 items() 中的每个键、值，执行
- 如果值与 1 相同，则
  - flag := 1
  - break
如果 flag 与 1 相同，则
- 返回 False
返回 True
从主方法执行以下操作 −
- 当 check_perfect_pow(n) 为 False 且 check_strong_num(n) 为 True 时返回 True，否则返回false

示例

让我们看看下面的实现，以便更好地理解 −

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))