番号がPythonのトロイの木馬番号であるかどうかを確認します

番号nがあるとすると、nがトロイの木馬番号であるかどうかを確認する必要があります。私たちが知っているように、トロイの木馬の数は、完全な力のない強い数です。素数除数またはnの因数pごとに、p ^ 2も除数である場合、数nは強い数です。言い換えれば、すべての素因数が少なくとも2回出現します。トロイの木馬の数は多いです。しかし、その逆は真実ではありません。つまり、すべての強い数字がトロイの木馬の数字であるとは限りません。a^bとして表すことができない数字だけです。

したがって、入力が72のような場合、72は（6 * 6 * 2）=（6 ^ 2 * 2）として表すことができるため、出力はTrueになります。強力な数ですが、完全な力はありません。

これを解決するには、次の手順に従います-

• 関数check_perfect_pow（）を定義します。これにはnがかかります
• nが1と同じ場合、
  • Trueを返す
• 範囲2から（nの平方根）+ 1の整数部分のxの場合、do
  • y：=2
  • p =x ^ y
  • p <=nおよびp> 0の場合、do
    • 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
• フラグ：=0
• 各キーについて、countのitems（）の値を実行します
  • 値が1と同じ場合、
    • フラグ：=1
    • 休憩
• フラグが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