快速確定數字是否分割集合中的任何元素

是否有算法可以快速確定數字是否是給定數字集合的因子？快速確定數字是否分割集合中的任何元素

例如，12是因子[24,33,52]而5不是。

難道還有比線性搜索O(n)一個更好的辦法？該集合將包含幾百萬個元素。我不需要找到這個號碼，只是一個true或false的結果。

2012-05-08 user1350004

聽起來就像你正在尋找** integer factorisation **。 AFAIK，這不是在量子計算之外存在多項式時間解的問題。 –

是否訂購了集合？該集的元素範圍是否受到任何限制？最佳算法總是依賴於良好的數據知識，如果你知道更多，告訴我們更多。 –

該集可以排序。元素的範圍在0 - 10^12之間。 – user1350004

我想一般O（n）的搜索是你到底是什麼了。但是，根據數字的大小，通過觀察如果您正在尋找可以被D整除的數字，並且您具有可以被D整除的數字，則可以在相當程度上加快搜索速度（假設您可以這樣做）當前掃描的x和x是不是由d整除，下一個可能的候選顯然在地板（[X + d]/d）* D.即，如果d = 12，該列表是

5 11 13 19 22 25 27

和您正在掃描13，下一個可能的候選號碼將是24.現在取決於您的輸入分佈，您可以使用二進制搜索而不是線性搜索向前掃描，因爲您正在搜索的最少號碼不小於24在列表中，並且列表被排序。如果D很大，那麼你可以通過這種方式節省大量的比較。

然而但從純計算複雜性點，排序和然後搜索將是爲O（n log n）的，而只是一個線性掃描爲O（n）。

來源

2012-05-08 10:58:57

如果對一個恆定的列表進行檢查大量數字的一個可能的方法來加快這一進程是在列表中的第一個數字因式分解到他們的首要因素。然後將列表成員放在字典中，並將主要因素作爲關鍵字。然後，當一個數字（潛在因素）出現時，您首先將其分解爲其主要因素，然後使用構造的字典來檢查數字是否是可能是給定數字的可能倍數的數字的因子。

來源

2012-05-08 11:13:07 fireant

測試許多潛在因素對恆定的設定，你應該意識到，如果設定的一個元素只是兩個人的多，這是不相關的，可以刪除。這種方法是一種被稱爲Sieve of Eratosthenes的古老算法的變體。交易測試考生的數量龐大，當啓動時間爲運行時間：

選擇在設置最小數> 1
刪除號碼，的任何倍數除了本身，從集
對於下一個最小的數字重複2，進行一定次數的迭代。迭代的次數將取決於與啓動時間的權衡

您現在剩下一個小得多的組，以進行徹底測試。爲了提高效率，您需要一個允許O（1）刪除的數據結構，就像鏈接列表一樣，或者只需用零替換「已刪除」的元素，然後將非零元素複製到新的容器中。

來源

2012-05-08 11:36:16 smocking

我不知道這個問題的，所以讓我問另一個：是12 [6,33,52]的一個因素？很明顯，12沒有劃分6,33或52，但12的因子是2 * 2 * 3，因子6,33和52是2 * 2 * 2 * 3 * 3 * 11 * 13。所有12個因素都以充分的多樣性出現在集合[6,33,52]中，所以你可以說12是[6,33,52]的一個因子。

如果你說12不是[6,33,52]的一個因子，那麼沒有更好的解決方案，比用12來測試每個數字的整除還要好。只需執行劃分並檢查剩餘部分。因此6％12 = 6,33％12 = 9和52％12 = 4，因此12不是[6.33.52]的因數。但是，如果你說12 爲 [6,33,52]，然後才能確定的因素，如果一些˚F是一套NS的因素，只是乘以數量NS一起順序，後每個乘法取餘數模˚F，報告真正立即如果餘數爲0過，如果你達到數的列表的末尾報告假納秒無0

餘我們舉兩個例子。首先，12是[6,33,52]的一個因素？第一個（平凡）乘法結果爲6並給出了6的餘數。現在6 * 33 = 198，除以12得到餘數6，並且我們繼續。現在6 * 52 = 312和312/12 = 26r0，所以餘數爲0，結果爲true。其次，5是[24,33,52]的一個因素？乘法鏈是24％5 = 5，（5 * 33）％5 = 2和（2 * 52）％5 = 4，所以5不是[24,33,52]的因子。

該算法的一個變體最近用於attack RSA密碼系統;你可以閱讀關於攻擊是如何工作的here。

來源

2012-05-08 13:49:22 user448810

由於要搜索的集合是固定的，因此組織搜索集合的任何時間都將花費時間。如果你可以在內存中獲取該集合，那麼我期望二叉樹結構適合。平均在二叉樹中搜索元素是O(log n)操作。

如果您有理由相信集合中的數字均勻分佈在整個範圍[0..10^12]那麼對存儲器中已排序集合的二進制搜索應該執行以及搜索二叉樹。另一方面，如果集合（或集合的任何子集）中的中間元素預計不會接近集合（或子集）所包含範圍內的中間值，那麼我認爲二叉樹會更好（實際）表現。

如果你不能在內存中獲取整個集合，然後將其分解成適合內存的塊和將這些塊存儲在磁盤上可能是一種方式。您可以將集合的根分支和上分支存儲在內存中，並使用它們索引到磁盤上。保存在內存中的那部分樹的深度是你應該自己決定的，但是如果你需要比根和分支的兩級更多的東西，在磁盤上給出8塊，我會感到驚訝。

當然，這隻能解決你的問題的一部分，找到給定的數字是否在集合中;你真的想知道給定的數字是否是集合中任何數字的因子。正如我在評論中所建議的那樣，我認爲任何基於對該集合中的數字進行因式分解的方法都是毫無希望的，給出了超出多項式時間的預期運行時間。

我會以相反的方式處理這部分問題：生成給定數字的倍數並搜索它們中的每一個。如果您的套件有10^7元素，則任何給定編號N的套件中將有大約(10^7)/N倍數。如果從[0..10^12]範圍內隨機抽取給定數字，則N的平均值爲0.5*10^12，這表明（與直覺相反），在大多數情況下，您只需搜索N本身。

是的，我知道在很多情況下，您將不得不搜索更多的值。

這種方法將相對容易並行。

來源

2012-05-08 14:15:10

一個快速解決方案，它需要一些預先計算：

整理一套二叉樹的規則如下：一組

數字是在葉子上。
樹的根包含r所有素數的最小值，它們除以一組數。
左子樹對應於r的倍數的子集（除以r以便r將不會無限重複）。
右子樹對應於不是r的倍數的子集。

如果你想測試一個數除以N設定的一些要素，計算它的素數分解並辦理樹，直到到達葉。如果葉片包含數字，則N將其分開，否則，如果葉片爲空，則N不會將該組中的元素分開。

來源

2012-05-08 23:09:45 Thomash

只需計算該組的乘積並用測試因子對結果進行修改即可。在您的例子 {24,33,52} P = 41184

TF 12：41184模12 = 0真 TF 5：41184 MOD 5 = 4假

該組可以被分成塊，如果計算產品會溢出計算器的算術運算，但通過存儲字符串可能會產生大量數字。

來源

2017-07-10 11:45:52

快速確定數字是否分割集合中的任何元素

回答

相關問題