ตรวจสอบว่าตัวเลขเป็นหมายเลขโทรจันใน Python . หรือไม่

สมมติว่าเรามีหมายเลข n เราต้องตรวจสอบว่า n เป็นหมายเลขโทรจันหรือไม่ อย่างที่เราทราบกันดีว่าหมายเลขโทรจันเป็นตัวเลขที่เป็นตัวเลขที่แข็งแกร่งแต่ไม่มีกำลังสมบูรณ์ จำนวน n เป็นจำนวนหนักเมื่อสำหรับทุกตัวหารเฉพาะหรือตัวประกอบ p ของ n p^2 เป็นตัวหารด้วย กล่าวอีกนัยหนึ่ง ทุกปัจจัยเฉพาะปรากฏขึ้นอย่างน้อยสองครั้ง ตัวเลขโทรจันนั้นแข็งแกร่ง แต่กลับไม่เป็นความจริง ดังนั้นจึงหมายความว่า ไม่ใช่ตัวเลขที่แข็งแกร่งทั้งหมดที่เป็นตัวเลขโทรจัน:เฉพาะตัวเลขที่ไม่สามารถแสดงเป็น a^b ได้

ดังนั้น หากอินพุตเท่ากับ 72 เอาต์พุตจะเป็น True เนื่องจาก 72 สามารถแสดงเป็น (6*6*2) =(6^2 * 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
คืนค่าเท็จ
กำหนดฟังก์ชัน check_strong_num() นี่จะใช้เวลา n
นับ :=แผนที่เก็บความถี่ของตัวเลข เริ่มต้นทั้งหมดเป็น 0
ในขณะที่ n mod 2 เหมือนกับ 0, do
- n :=n / 2 (การหารจำนวนเต็ม)
- นับ[2] :=นับ[2] + 1
สำหรับฉันในช่วง 3 ถึงส่วนของจำนวนเต็มของ (รากที่สองของ n) + 1 เพิ่มขึ้น 2 ทำ
- ในขณะที่ n mod i เหมือนกับ 0, do
  - n :=n / i (การหารจำนวนเต็ม)
  - นับ[i] :=นับ[i] + 1
ถ้า n> 2 ไม่ใช่ศูนย์ ดังนั้น
- นับ[n] :=นับ[n] + 1
ธง :=0
สำหรับแต่ละคีย์ ค่าใน items() ของการนับ ทำ
- ถ้าค่าเท่ากับ 1 แล้ว
  - ธง :=1
  - แตก
ถ้าแฟล็กเหมือนกับ 1 แล้ว
- คืนค่าเท็จ
คืนค่า True
จากวิธีหลัก ให้ทำดังต่อไปนี้ −
- คืนค่า จริง เมื่อ check_perfect_pow(n) เป็นเท็จ และ check_strong_num(n) เป็นจริง มิฉะนั้น คืนค่าเท็จ

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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))

อินพุต

ผลลัพธ์

True