คู่องค์ประกอบที่แตกต่างของ co-prime ที่เป็นไปได้ทั้งหมดภายในช่วง [L, R]?

เราจะมาดูวิธีการนับจำนวนคู่ของ co-prime จากช่วง โดยที่ตัวเลขจะไม่ปรากฏมากกว่าคู่เดียว

ก่อนจะพูดถึงตรรกะ เรามาดูกันก่อนว่าจำนวนโคไพรม์คืออะไร? จำนวนเฉพาะร่วมคือตัวเลขที่มีตัวหารจำนวนเต็มบวกเพียงตัวเดียว นั่นคือ 1 กล่าวคือ เราสามารถพูดได้ว่า GCD ของตัวเลขสองตัวนี้คือ 1

ที่นี่เราให้ขีด จำกัด ล่างและบน หากขีด จำกัด ล่างและบนเป็น 1 และ 6 แสดงว่ามีสามคู่ ได้แก่ (1, 2), (3, 4) และ (5, 6)

แนวทางในการแก้ปัญหานี้ก็คือ ถ้าตัวเลขเรียงต่อกัน จะเป็น co-prime เสมอ ดังนั้นการนับจะเป็น (R – L + 1)/2 ถ้า (R – L + 1) เป็นเลขคี่ ก็จะเหลือหนึ่งเลข นั้นจะไม่อยู่ในคู่ใด ๆ หากเป็นคู่ ทั้งหมดจะทำให้เป็นคู่

อัลกอริทึม

countCoPrimePairs(L, R)

Begin
   return (R – L + 1)/2
End

ตัวอย่าง

#include <iostream>
using namespace std;
int countCoPrimePairs(int L, int R) {
   return (R - L + 1)/2;
}
main() {
   int l = 1, r = 6;
   cout << "Number of co-prime pairs: " << countCoPrimePairs(l, r);
}

ผลลัพธ์

Number of co-prime pairs: 3