資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學使用C++查詢不能被[2, 10]範圍內任何數整除的數字
在這篇文章中，我們將討論如何找到從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整除，能被3整除的數字都能被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等）編寫此程式。我們希望您覺得這篇文章有幫助。
更新於：2021年11月26日
711 次瀏覽
廣告