โจทย์: กำหนดช่วง [n, m] หาจำนวนเต็มในช่วงที่มีตัวประกอบ (factors) เป็นจำนวนคี่
ข้อสังเกตทางคณิตศาสตร์
เฉพาะจำนวนที่เป็น Perfect Square (ยกกำลังสอง) เท่านั้นที่มีตัวประกอบเป็นจำนวนคี่ เพราะตัวประกอบมักมาคู่กัน (a × b = n) ยกเว้น √n × √n
สูตร
จำนวน Perfect Square ใน [n, m] = ⌊√m⌋ - ⌊√(n-1)⌋
ตัวอย่างโค้ด Python
def count_odd_factors(n, m):
"""นับจำนวนที่มีตัวประกอบคี่ในช่วง [n, m]"""
return int(m**0.5) - int((n-1)**0.5)
# ทดสอบ
n, m = 25, 400
print("Number of odd squares are:", count_odd_factors(n, m))
# Output: 16 (25, 36, 49, ..., 400)
ผลลัพธ์
Number of odd squares are: 16
อธิบาย
Perfect squares ระหว่าง 25-400: 5²=25, 6²=36, ..., 20²=400 รวม 16 ตัว (5 ถึง 20)
ความซับซ้อน: Time O(1), Space O(1) - คำนวณได้ทันทีไม่ต้องลูป
