ลำดับจำนวนเฉพาะสัมพัทธ์
จำนวน \(a\) และ \(b\) เป็นจำนวนเฉพาะสัมพัทธ์ (coprime) เมื่อตัวหารร่วมมาก (GCD) ของทั้งสองเท่ากับ 1 GCD คือจำนวนบวกที่มากที่สุดที่หาร \(a\) และ \(b\) ได้ลงตัว ตัวอย่างเช่น 7 และ 9 เป็นจำนวนเฉพาะสัมพัทธ์ เพราะ GCD ของทั้งสองคือ 1
กำหนดให้มีสองลิสต์คือ list1 และ list2 โจทย์ต้องการให้สร้างลิสต์ใหม่ชื่อ coprimes ที่เก็บคู่จำนวนเฉพาะสัมพัทธ์ทั้งหมดจาก list1 และ list2
แต่ก่อนอื่น ให้เขียนฟังก์ชันสำหรับหา GCD โดยใช้อัลกอริทึมต่อไปนี้:
- ตรวจสอบว่า \(b = 0\) หรือไม่
- ถ้าใช่ ให้คืนค่า \(a\) เป็น GCD ของ \(a\) และ \(b\)
- ถ้าไม่ใช่ ให้ไปขั้นตอนที่ 2
- แทนค่าใหม่โดย \(a \leftarrow b\) และ \(b \leftarrow a \% b\)
- กลับไปที่ขั้นตอนที่ 1
แบบฝึกหัดนี้เป็นส่วนหนึ่งของหลักสูตร
ฝึกทำโจทย์สัมภาษณ์งานเขียนโค้ดด้วย Python
แบบฝึกหัดเชิงโต้ตอบแบบลงมือทำ
ลองทำแบบฝึกหัดนี้โดยเติมโค้ดตัวอย่างนี้ให้สมบูรณ์
def gcd(a, b):
# Define the while loop as described
while ____:
temp_a = ____
a = ____
b = ____
# Complete the return statement
return ____