這個矢量數組代碼做什麼？ （C++）

Question

難以找到對此的解釋。

這段代碼做了什麼？我知道它創建了一個矢量數組，但這就是它。 如何打印矢量數組和訪問元素以進行實驗？

#define MAXN 300009 
vector<int>dv[MAXN]; 
int main() 
{ 
    for(int i=1;i<MAXN;i++) 
    for(int j=i;j<MAXN;j+=i) 
     dv[j].push_back(i); 
} 

Answer 1

該代碼很容易測量。它最終產生的現實是一個非常簡單的（並且效率很低）Sieve of Eratosthenes。瞭解這個算法，你會看到這段代碼是如何產生這種效果的。

編輯：它也是一個因子表生成器。請看下面的編輯。

之後檢測代碼並轉儲輸出，並減少循環次數以簡化我們的代碼。我們使用range-based-for環爲向量的陣列中的枚舉在每個向量：

#include <iostream> 
#include <vector> 

#define MAXN 20 
std::vector<int>dv[MAXN]; 

int main() 
{ 
    for(int i=1;i<MAXN;i++) 
    { 
     for(int j=i;j<MAXN;j+=i) 
      dv[j].push_back(i); 
    } 

    for (auto const& v : dv) 
    { 
     for (auto x : v) 
      std::cout << x << ' '; 
     std::cout << '\n'; 
    } 
} 

產生的輸出是：

1 
1 2 
1 3 
1 2 4 
1 5 
1 2 3 6 
1 7 
1 2 4 8 
1 3 9 
1 2 5 10 
1 11 
1 2 3 4 6 12 
1 13 
1 2 7 14 
1 3 5 15 
1 2 4 8 16 
1 17 
1 2 3 6 9 18 
1 19 

現在，請注意，只有元件每個矢量（1和一個附加號碼）。第二個號碼是素數。在我們的測試案例中，這兩個元素向量是：

1 2 
1 3 
1 5 
1 7 
1 11 
1 13 
1 17 
1 19 

簡而言之，這是一個非常簡單並且非常低效的找到素數的方法。因此，輸出循環的輕微變化僅輸出長度爲2的所有矢量的第二個元素，因此會生成低於MAXN的所有素數。因此，使用：

for (auto const& v : dv) 
{ 
    if (v.size() == 2) 
     std::cout << v[1] << '\n'; 
} 

我們會得到[2...MAXN)

---

編輯所有素數：因數表生成

如果不是很明顯，每個向量都有一個結束元素（不巧合地也與外部陣列的下標對齊）。所有前面的因素構成了這個數字的積極因素。例如：

1 2 5 10 

是dv[10]向量，並告訴你10具有因素1,2,5,10。同樣，

1 2 3 6 9 18 

是dv[18]向量，並告訴你18具有因素1,2,3,6,9,18。

總之，如果有人想知道某些N號碼的所有因素，即< MAXN，這將是一種將所有信息放入表格的方式。