การหาตัวเลขที่ไม่หารด้วยตัวเลขในช่วง [2, 10] ลงตัว โดยใช้ C++

ในบทความนี้ เราจะอภิปรายปัญหาการหาตัวเลขจาก 1 ถึง n (ที่กำหนด) ซึ่งไม่สามารถหารด้วยตัวเลขใดๆ จาก 2 ถึง 10 ลงตัวได้ มาทำความเข้าใจด้วยตัวอย่าง:

Input : num = 14
Output : 3
คำอธิบาย: มีตัวเลข 3 ตัว คือ 1, 11, และ 13 ที่ไม่หารลงตัว

Input : num = 21
Output : 5
คำอธิบาย: มีตัวเลข 5 ตัว คือ 1, 11, 13, 17, และ 19 ที่ไม่หารลงตัว

วิธีการแก้ปัญหา

วิธีง่าย (Simple Approach)

ถ้าเราตรวจสอบทุกตัวเลขจาก 1 ถึง num ว่ามันสามารถหารด้วยตัวเลขใดๆ จาก 2 ถึง 10 ลงตัวได้หรือไม่ ถ้าไม่ได้ ให้เพิ่มตัวนับ แต่วิธีนี้จะใช้เวลามากเกินไป ทำให้ความซับซ้อนด้านเวลาเพิ่มขึ้น

วิธีที่มีประสิทธิภาพ (Efficient Approach)

วิธีที่ดีที่สุดที่เราคิดได้คือ หาตัวเลขจาก 1 ถึง num ที่หารด้วยตัวเลขในช่วง [2, 10] ลงตัวก่อน แล้วลบจำนวนนี้ออกจาก num

ก่อนอื่น เราต้องหาตัวเลขทั้งหมดที่หารด้วย 2, 3, 4, 5, 10 ลงตัว แต่ตัวเลขที่หารด้วย 4, 6, 8, 10 ลงตัว จะหารด้วย 2 ลงตัว และตัวเลขที่หารด้วย 3 ลงตัว จะหารด้วย 6 และ 9 ลงตัว

เราต้องหาตัวเลขทั้งหมดที่หารด้วย 2, 3, 5, และ 7 ลงตัว และเราสามารถคำนวณได้จากหลักการรวม-ตัดออก (Inclusion-Exclusion Principle)

หลักการรวม-ตัดออก (Inclusion-Exclusion Principle)

ระบุว่าเราควรรวมขนาดของทุกเซตเดี่ยว คุณควรตัดออกขนาดของการตัดกันคู่ ขนาดของการตัดกันของเซตสามเซตควรเพิ่ม และต่อไป

สูตรเพื่อหาตัวเลขทั้งหมดคือ:

= NUM - X + Y - Z + A.

โดยที่:

X = ตัวเลขที่หารด้วย 2, 3, 5, 7 ลงตัว ( [num/2] + [num/3] + [num/5] + [num/7] )
Y = ตัวเลขที่หารด้วย (2,3), (2,5), (2,7), (3,5), (3,5), (3,7) และ (5,7) ลงตัว
  = ( [num/(2×3)] + [num/(2×5)] + [num/(2×7)] + [num/(3×5)] + [num/(3×7)] + [num/(5×7)] )
Z = ตัวเลขที่หารด้วย (2,3,5), (2,3,7), (2,5,7) และ (3,5,7) ลงตัว
  = ( [num/(2×3×5)] + [num/(2×3×7)] + [num/(2×5×7)] + [num/(3×5×7)] )
A = ตัวเลขที่หารด้วย (2,3,5,7) ลงตัว
  = ( [num/(2×3×5×7)] )

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n = 21, result;
    // ใช้สูตรจากหลักการรวม-ตัดออก
    // เพื่อหาจำนวนตัวเลขที่ไม่หารด้วยตัวเลขใดๆ จาก 2 ถึง 10 ลงตัว
    result = n - n/2 - n/3 - n/5 - n/7
             + n/6 + n/10 + n/14 + n/15 + n/21 + n/35
             - n/30 - n/42 - n/70 - n/105 + n/210;
    cout << "The count of numbers, not div by [2, 10] is: " << result;
    return 0;
}

ผลลัพธ์

The count of numbers, not div by [2, 10] is: 5

สรุป

ในบทความนี้ เราอภิปรายวิธีการหาตัวเลขที่ไม่หารลงตัวจาก 2 ถึง n เพื่อแก้ปัญหานี้ เราอภิปรายหลักการรวม-ตัดออก (Inclusion-Exclusion Principle) เรายังอภิปรายโปรแกรม C++ เพื่อนำวิธีการไปใช้เพื่อได้ผลลัพธ์ด้วยความซับซ้อน O(1) คุณสามารถเขียนโปรแกรมนี้ในภาษาอื่นๆ เช่น Java, C, Python ฯลฯ ได้ เราหวังว่าบทความนี้จะเป็นประโยชน์