โจทย์: กำหนดเลข n หาผลคูณของเฉพาะตัวประกอบที่ไม่ซ้ำกันทั้งหมด
ตัวอย่าง: n=11 → ผลคูณ = 11 (เพราะ 11 เป็นเฉพาะตัวประกอบเพียงตัวเดียว)
วิธี 1: Brute Force (for loop + prime check)
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 *= i
return product
print(productPrimeFactors(18))ผลลัพธ์
120
วิธี 2: Efficient (หาร 2 แล้ว หารเลขคี่จน sqrt(n))
import math
def productPrimeFactors(n):
product = 1
# หาร 2
if n % 2 == 0:
product *= 2
while n % 2 == 0:
n //= 2
# n เป็นคี่ ตอนนี้
for i in range(3, int(math.sqrt(n)) + 1, 2):
if n % i == 0:
product *= i
while n % i == 0:
n //= i
# ถ้า n > 2 แสดงว่า n เป็นเฉพาะ
if n > 2:
product *= n
return product
print(int(productPrimeFactors(8)))ผลลัพธ์
2
สรุป
เรียนรู้ 2 วิธีหาผลคูณเฉพาะตัวประกอบที่ไม่ซ้ำ: Brute force และ Efficient method (หาร 2 แล้ว หารเลขคี่ถึง sqrt)
