【笔记】算法记录

1、求一个数的素因子（试除法）

// 获取一个数的所有素因子
set<int> getPrimeFactors(int num) {
    set<int> primeFactors;
    for (int i = 2; i * i <= num; ++i) {
        while (num % i == 0) {
            primeFactors.insert(i);
            num /= i;
        }
    }
    if (num > 1) {
        primeFactors.insert(num);
    }
    return primeFactors;
}

2、计算集合的交集

#include <algorithm>
#include <set>

set<int> commonFactors, primeFactors, intersection;
set_intersection(commonFactors.begin(), commonFactors.end(), 
                primeFactors.begin(), primeFactors.end(), 
                inserter(intersection, intersection.begin()));

这段代码的作用

这段代码使用了 C++ 标准库中的 set_intersection 函数，它计算两个集合（commonFactors 和 primeFactors）的交集，并将结果存入 intersection 集合中。以下是每个部分的详细说明：

代码解析

1. set_intersection 函数：

   • 这是 <algorithm> 头文件中的标准函数，用于计算两个已排序范围的交集。
   • 它需要输入的集合是升序排序的，而 C++ 的 std::set 默认就是升序排列，因此可以直接使用。

2. 参数说明：

   • commonFactors.begin(), commonFactors.end()：第一个集合的范围，表示当前的公共素因子集合。
   • primeFactors.begin(), primeFactors.end()：第二个集合的范围，表示当前数的所有素因子集合。
   • inserter(intersection, intersection.begin())：一个插入迭代器，用于将交集结果插入到 intersection 集合中。

3. 执行逻辑：

   • 遍历两个集合，找出同时存在于两个集合中的元素。
   • 将这些共同的元素存入 intersection 集合。

4. 结果：

   • 交集计算完成后，intersection 集合包含了两个集合中共同的素因子。

3、