Python 中判断一个数是否为特洛伊数

假设我们有一个数字 n，我们需要检查 n 是否为特洛伊数。特洛伊数是一个强数，但不是完全幂。当 n 的每个素因子 p，p² 也是其因子时，n 为强数。换句话说，每个素因子至少出现两次。特洛伊数是强数，但反之不然。这意味着，并非所有强数都是特洛伊数：只有那些不能表示为 a^b 的数才是特洛伊数。

因此，如果输入是 72，则输出为 True，因为 72 可以表示为 (6*6*2) = (6² * 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
  • 对于 i 从 3 到 ⌊√n⌋ + 1，步长为 2，执行循环：
    • 当 n mod i 等于 0 时，执行循环：
      • n := n / i （整数除法）
      • count[i] := count[i] + 1
  • 如果 n > 2 且不为零，则
    • count[n] := count[n] + 1
  • flag := 0
  • 对于 count 的每个键值对，执行循环：
    • 如果 value 等于 1，则
      • flag := 1
      • 中断循环
  • 如果 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))

输入

72

输出

True

更新于：2020年8月27日

104 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告