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

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

Input : num = 14
Output : 3
Explanation: There are three numbers, 1, 11, and 13, which are not divisible.

Input : num = 21
Output : 5
Explanation: There are five numbers 1, 11, 13, 17, and 19, which are not divisible.

แนวทางในการหาทางออก

แนวทางง่ายๆ

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

แนวทางที่มีประสิทธิภาพ

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

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

เราจำเป็นต้องหาจำนวนทั้งหมดที่หารด้วย 2, 3, 5 และ 7 ลงตัว และสิ่งนี้เราสามารถคำนวณได้จากหลักการรวม-การยกเว้น

หลักการรวม-ยกเว้น

มันระบุว่าเราควรรวมขนาดของทุกชุดเดียว คุณควรลบขนาดของทางแยกคู่ ควรเพิ่มขนาดของสามชุดของสี่แยกทั้งหมด และอื่น ๆ

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

= NUM – X + Y – Z + A.

ที่ไหน

X = num divisible by 2, 3, 5, 7 ( [num / 2] + [num / 3] + [num / 5] + [num / 7] )

Y = num divisible by (2,3), (2, 5), (2, 7), (3, 5), (3, 5), (3, 7) and (5, 7) = ( [num / (2 * 3)] + [num / (2 * 5)] + [num / (2 * 7)] + [num / (3 * 5)] + num / (3 * 7)] + [num / (5 * 7)] ).

Z = num divisible by (2, 3, 5), (2, 3, 7), (2, 5, 7) and (3, 5, 7) = ( [num / (2 * 3 * 5)] + [num / (2 * 3 * 7)] + [num / (2 * 5 * 7)] + [num / (3 * 5 * 7)] )

A = num divisible by (2, 3, 5, 7) = ( [num / (2 * 3 * 5 * 7)] )

ตัวอย่าง

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

int main() {
   int n = 21, result;
   // applying formula from inclusion - exclusion principle
   // to find the count of numbers not divisible by any number from 2 to 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 เพื่อแก้ปัญหานี้ เราได้พูดถึงหลักการรวม-การยกเว้น เรายังพูดถึงโปรแกรม C++ เพื่อใช้แนวทางเพื่อให้ได้ผลลัพธ์ด้วยความซับซ้อนของ O(1) คุณสามารถเขียนโปรแกรมนี้ในภาษาอื่นๆ เช่น Java, C, Python เป็นต้น เราหวังว่าคุณจะพบว่าบทความนี้มีประโยชน์