숫자가 Python에서 아킬레스 숫자인지 확인하십시오.

숫자 n이 있다고 가정합니다. n이 아킬레스 수인지 아닌지 확인해야 합니다. 우리가 알고 있듯이 숫자는 강력한 숫자일 때 아킬레스 수입니다(수 N은 모든 소인수 p에 대해 p^2도 나눌 때 강력한 숫자라고 함). 그러나 완전한 거듭제곱은 아닙니다. 아킬레스 수의 몇 가지 예는 다음과 같습니다:72, 108, 200, 288, 392, 432, 500, 648, 675, 800, 864, 968, 972, 1125.

따라서 입력이 108과 같으면 6과 36이 모두 나누기 때문에 완전제곱수가 아니기 때문에 출력은 True가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• check_powerful() 함수를 정의합니다. n
소요됩니다.
• n mod 2가 같을 때 수행
  • p :=0
  • n mod 2가 0과 같을 때 do
    • n :=n / 2
    • p :=p + 1
  • p가 1과 같으면
    • 거짓을 반환
• p :=(n의 제곱근) + 1의 정수
• 3~p 범위의 인수에 대해 2만큼 증가, do
  • p :=0
  • n mod factor가 0일 때 do
    • n :=n / 인수
    • p :=p + 1
  • p가 1과 같으면
    • 거짓을 반환
• (n이 1과 같을 때) true를 반환
• check_power() 함수를 정의합니다. 시간이 걸립니다
• a가 1과 같으면
  • 참 반환
• p :=(n의 제곱근) + 1의 정수
• 범위 2의 i에 대해 1만큼 증가, do
  • val :=log(a) / log(i) [모든 밑수 e]
  • if (val - (val)의 정수 부분) <0.00000001, then
    • 참 반환
• 거짓을 반환
• 메인 방법에서 다음을 수행하십시오. -
• check_powerful(n)이 True와 같고 check_power(n)이 False와 같으면
  • 참 반환
• 그렇지 않으면
  • 거짓을 반환

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

from math import sqrt, log
def check_powerful(n):
   while (n % 2 == 0):
      p = 0
      while (n % 2 == 0):
         n /= 2
         p += 1
      if (p == 1):
         return False  
   p = int(sqrt(n)) + 1
   for factor in range(3, p, 2):
      p = 0
      while (n % factor == 0):
         n = n / factor
         p += 1
      if (p == 1):
         return False
   return (n == 1)
def check_power(a):
   if (a == 1):
      return True
   p = int(sqrt(a)) + 1
   for i in range(2, a, 1):
      val = log(a) / log(i)
      if ((val - int(val)) < 0.00000001):
         return True
   return False
def isAchilles(n):
   if (check_powerful(n) == True and check_power(n) == False):
      return True
   else:
      return False
n = 108
print(isAchilles(n))

입력

108

출력

True