All Factors of the Product of a List of Distinct Primes | tech::interview

All Factors of the Product of a List of Distinct Primes | tech::interview

Print all factors of the product of a given list of distinct primes.
Example:
Input: 2 3 7
Output: 1 2 3 6 7 14 21 42

G家题，很简单的DFS，每个prime选或不选即可。

void all_factors(const vector<int>& primes) {

    function<void(int,int)> dfs = [&](int id,int cur) {

        if(id == primes.size()) {

            cout << cur << endl;

            return;

        }        

        dfs(id + 1, cur);

        dfs(id + 1, cur * primes[id]);

    };    

    dfs(0,1);

}

Read full article from All Factors of the Product of a List of Distinct Primes | tech::interview