โปรแกรม Python หาผลคูณของเฉพาะตัวประกอบที่ไม่ซ้ำกันของตัวเลข

ในบทความนี้ เราจะเรียนรู้วิธีแก้ปัญหาตามข้อความปัญหาที่กำหนดด้านล่าง −

ข้อความของปัญหา − กำหนดตัวเลข n เราต้องหาผลคูณของเฉพาะตัวประกอบที่ไม่ซ้ำกันทั้งหมดของมันและคืนค่า

ตัวอย่าง

Input: num = 11
Output: Product is 11
Explanation: ตัวเลขอินพุตคือ 11 มีเฉพาะตัวประกอบเพียงตัวเดียวคือ 11 เอง ดังนั้นผลคูณคือ 11

แนวทางที่ 1

ใช้ลูป for จาก i = 2 ถึง n+1 ตรวจสอบว่า i เป็นตัวประกอบของ n และตรวจสอบว่า i เป็นจำนวนเฉพาะหรือไม่ ถ้าใช่ ให้เก็บผลคูณในตัวแปร product และดำเนินต่อไปจนกว่า i จะเท่ากับ n

ตัวอย่าง

def productPrimeFactors(n):
    product = 1
    for i in range(2, n + 1):
        if (n % i == 0):
            isPrime = 1
            for j in range(2, int(i / 2 + 1)):
                if (i % j == 0):
                    isPrime = 0
                    break
            if (isPrime):
                product = product * i
    return product

# main
n = 18
print(productPrimeFactors(n))

ผลลัพธ์

6

ขอบเขตของตัวแปรทั้งหมดแสดงในภาพด้านล่าง −

แนวทางที่ 2 (มีประสิทธิภาพมากกว่า)

• ในขณะที่ n หารด้วย 2 ลงตัว (เลขคู่) ให้พิมพ์ 2 และหาร n ด้วย 2

• หลังขั้นตอนที่ 1 n ต้องกลายเป็นเลขคี่ ตอนนี้เริ่มลูป for จาก i = 3 จนถึงรากที่สองของ n ในขณะที่ i หาร n ลงตัว ให้พิมพ์ i และหาร n ด้วย i หลังจาก i หาร n ไม่ลงตัว ให้เพิ่ม i ขึ้น 2 และดำเนินต่อ

• ถ้า n เป็นจำนวนเฉพาะและมากกว่า 2 n จะไม่กลายเป็น 1 ด้วยสองขั้นตอนข้างต้น ดังนั้นให้พิมพ์ n ถ้ามันมากกว่า 2

ตัวอย่าง

import math

def productPrimeFactors(n):
    product = 1
    # เฉพาะตัวประกอบ 2
    if (n % 2 == 0):
        product *= 2
        while (n % 2 == 0):
            n = n / 2
    # n ต้องเป็นเลขคี่
    for i in range(3, int(math.sqrt(n)), 2):
        # ในขณะที่ i หาร n ลงตัว พิมพ์ i และหาร n
        if (n % i == 0):
            product = product * i
            while (n % i == 0):
                n = n / i
    # n เป็นจำนวนเฉพาะมากกว่า 2
    if (n > 2):
        product = product * n
    return product

# main()
n = 8
print(int(productPrimeFactors(n)))

ผลลัพธ์

2

ขอบเขตของตัวแปรระบุในภาพด้านล่าง −

สรุป

ในบทความนี้ เราได้เรียนรู้เกี่ยวกับผลคูณของเฉพาะตัวประกอบที่ไม่ซ้ำกันของตัวเลขที่กำหนด ด้วยแนวทาง brute force และแนวทางที่มีประสิทธิภาพ