숫자 n이 있다고 가정하면 n이 트로이 목마 번호인지 여부를 확인해야 합니다. 알다시피 트로이 목마는 완전수가 없는 강한 숫자입니다. 모든 소수 또는 n의 인수 p에 대해 p^2도 제수일 때 숫자 n은 강한 숫자입니다. 즉, 모든 소인수는 적어도 두 번 나타납니다. 트로이 목마는 강력합니다. 그러나 그 반대는 사실이 아닙니다. 따라서 모든 강력한 숫자가 트로이 숫자가 아니라 ^b로 표시될 수 없는 숫자만 의미합니다.
따라서 입력이 72와 같으면 72가 (6*6*2) =(6^2 * 2)로 표시될 수 있으므로 출력은 True가 됩니다. 강력한 숫자지만 완벽한 힘이 없습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- check_perfect_pow() 함수를 정의합니다. n 소요됩니다.
- n이 1과 같으면
- 참 반환
- (n의 제곱근) + 1의 정수 부분까지 범위 2의 x에 대해
- y :=2
- p =x^y
- p <=n 및 p>
0인 동안 do
- p가 n과 같으면
- 참 반환
- y :=y + 1
- p =x^y
- p가 n과 같으면
- 거짓을 반환
- check_strong_num() 함수를 정의합니다. n 소요됩니다.
- count :=숫자의 빈도를 저장하는 맵, 처음에는 모두 0입니다.
- n mod 2가 0과 같을 때 do
- n :=n / 2(정수 나누기)
- count[2] :=count[2] + 1
- 범위 3에서 (n의 제곱근) + 1의 정수 부분까지 i에 대해 2만큼 증가, do
- n mod i가 0인 동안 do
- n :=n / i (정수 나누기)
- count[i] :=count[i] + 1
- n mod i가 0인 동안 do
- n> 2가 0이 아니면
- count[n] :=count[n] + 1
- 플래그 :=0
- 각 키에 대해, count의 items()에 있는 값, do
- 값이 1과 같으면
- 플래그 :=1
- 중단
- 값이 1과 같으면
- 플래그가 1과 같으면
- 거짓을 반환
- 참 반환
- 메인 메소드에서 다음을 수행하십시오 -
- 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