检查数字是否是Python中的特洛伊木马数字
假设我们有一个数字n,我们必须检查n是否是TrojanNumber。众所周知,特洛伊木马号是一个没有完善的幂的强数。当对于每个主除数或n的因子p,p^2也是一个约数时,数字n是一个强数。换句话说,每个素因数至少出现两次。特洛伊木马数字很强。但是事实并非如此。因此,这意味着并非所有强数都是特洛伊木马数字:只有那些不能表示为a^b的数字。
因此,如果输入类似于72,则输出将为True,因为72可以表示为(6*6*2)=(6^2*2)。强数,但没有完美的力量。
为了解决这个问题,我们将遵循以下步骤-
定义一个函数check_perfect_pow()。这将花费n
如果n与1相同,则
返回True
对于范围2到(n的平方根)+1的整数部分的x,执行
如果p与n相同,则
y:=y+1
p=x^y
返回True
y:=2
p=x^y
当p<=n并且p>0时,
返回False
定义一个函数check_strong_num()。这将花费n
count:=一个保存数字频率的映射,最初都是0
而nmod2与0相同,则
n:=n/2(整数除法)
count[2]:=count[2]+1
对于范围在3到(n的平方根)+1的整数部分的i,增加2,
n:=n/i(整数除法)
count[i]:=count[i]+1
当nmod我等于0时,
如果n>2为非零,则
count[n]:=count[n]+1
标志:=0
对于每个键,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